這是LeetCode上面一道難度為困難的題目，實際解決起來并不困難，有多種實現(xiàn)方法，在此記錄一下。

接雨水

給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。
由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖如下：

示例:

輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6

左右查找解法（暴力法）：

    private int trap(int[] height) {
        // 定義結(jié)果
        int res = 0;
        // 數(shù)組長度
        int len = height.length;
        // 過濾掉最左邊以及最右邊那個柱子，不可能蓄水
        for (int i = 1; i < len-1; i++) {
            // 用于保存i位置左邊以及右邊的最大值
            int left = 0,right = 0;
            for (int j=i;j>=0;j--) {
                left = Math.max(left,height[j]);
            }
            for (int j=i;j<len;j++) {
                right = Math.max(right,height[j]);
            }
            // 取左右兩邊的最大值中，小的那個，計算出i位置儲水量
            res += Math.min(left,right)-height[i];
        }
        return res;
    }

基于暴力法，通過保存左右遍歷最大值，解法二：

    private int trap(int[] height) {
        // 返回值
        int res = 0;
        int len = height.length;
        if (len<=1) return res;
        // 保存i位置下左邊的最大值
        int[] left = new int[len];
        // 保存i位置下右邊的最大值
        int[] right = new int[len];
        // 初始化left為第一個值
        left[0] = height[0];
        // 遍歷并保存i位置左側(cè)最大值
        for (int i=1;i<len;i++) {
            left[i] = Math.max(height[i],left[i-1]);
        }
        // 初始化right為數(shù)組末端第一個值
        right[len-1] = height[len-1];
        // 遍歷并保存i位置右側(cè)最大值
        for (int i=len-2;i>=0;i--) {
            right[i] = Math.max(height[i],right[i+1]);
        }
        // 已知i位置左右最大值，比較得到小值并減去當(dāng)前值，獲取儲水量
        for (int i=1;i<len-1;i++) {
            res+= Math.min(left[i],right[i])-height[i];
        }
        return res;
    }

使用棧來存儲坐標(biāo)：

    private int trap(int[] height) {
        // 定義一個棧，用來保存下標(biāo)
        Stack<Integer> stack = new Stack<>();
        int res = 0,cur = 0;

        while (cur<height.length) {
            // 如果棧不是空的，且當(dāng)前高度大于棧頂高度
            // 這時如果棧內(nèi)存在比棧頂更高的元素，則行成蓄水結(jié)構(gòu)
            while (!stack.isEmpty() && height[cur]>height[stack.peek()]) {
                // 彈出棧頂
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                // 獲取當(dāng)前位置到棧頂位置的寬度
                int distance = cur - stack.peek() - 1;
                // 計算當(dāng)前位置與棧頂位置的最小值，并獲得與彈出條的高度差
                int boundHeight = Math.min(height[cur],height[stack.peek()])-height[top];
                // 乘積并累加
                res += distance*boundHeight;
            }
            // 將當(dāng)前坐標(biāo)壓入棧
            stack.push(cur++);
        }
        // ex:[4,1,2,3]
        // cur = 2 ， res += 1(2到4的距離)*1（2-1）
        // cur = 3 ， res += 2(3到4的距離)*1（3-2）

        return res;
    }

雙指針解法：

private int trap_3(int[] height) {
        // 定義左右指針
        int left = 0,right = height.length-1;
        int res = 0;
        // 用于保存左右最大值
        int left_max = 0,right_max = 0;
        // 結(jié)束條件
        while (left<right) {
            // 如果左指針高度小于右指針
            if (height[left]<height[right]) {
                // 如果左指針高度大于左最大高度，更新左最大高度
                // 否則計算當(dāng)前蓄水值
                // 左指針右移一位
                if (height[left]>=left_max) {
                    left_max=height[left];
                } else {
                    res+=left_max-height[left];
                }
                left++;
            } else {
                // 左指針高度大于右指針時
                // 右指針高度大于右最大高度，更新右最大高度
                // 否則計算當(dāng)前蓄水值
                // 右指針左移一位
                if (height[right]>=right_max) {
                    right_max = height[right];
                } else {
                    res += right_max-height[right];
                }
                right--;
            }
        }
        // ex:[4,1,2,3]
        // => ex:[4(left,left_max),1,2,3(right,right_max)] 右指針小，右指針左移動一位
        // => ex:[4(left,left_max),1,2(right,res+=3-2),3(right_max)] 右指針小，右指針左移動一位
        // => ex:[4(left,left_max),1(right,res+=3-1),2,3(right_max)] 
        return res;
    }