Notebook online

接雨水

 算法

嗨害嗨，我接雨水又来了嗷，为什么三番五次的讲这个题目呢？因为这题实在是太经典了，好的题目无论做多少遍都是值得的，常做常新的。

先看题目，废话不多说，家人们，上链接

jieyushui.png

核心思路

对于此题从局部到整体，比如位置i，装水大小取决于左右两边最高柱子的最小值，分别称这两个柱子高度为l_max和r_max；位置 i 最大的水柱高度就是min(l_max, r_max)

代码实现

1
2
3
4
5
6

water[i] = min(
               # 左边最高的柱子
               max(height[0..i]),  
               # 右边最高的柱子
               max(height[i..end]) 
            ) - h

一个简单的暴力解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int trap(int[] height) {
    int n = height.length;
    int res = 0;
    for (int i = 1; i < n - 1; i++) {
        int l_max = 0, r_max = 0;
        // 找右边最高的柱子
        for (int j = i; j < n; j++)
            r_max = Math.max(r_max, height[j]);
        // 找左边最高的柱子
        for (int j = i; j >= 0; j--)
            l_max = Math.max(l_max, height[j]);
        // 如果自己就是最高的话，
        // l_max == r_max == height[i]
        res += Math.min(l_max, r_max) - height[i];
    }
    return res;
}

双指针

我们用双指针边走边算，节省下空间复杂度，这个问题要这么思考，我们只在乎min(l_max, r_max)。我们已经知道l_max < r_max了，至于这个r_max是不是右边最大的，不重要，重要的是height[i]能够装的水只和较低的l_max之差有关

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int l_max = 0, r_max = 0;

    int res = 0;
    while (left < right) {
        l_max = Math.max(l_max, height[left]);
        r_max = Math.max(r_max, height[right]);

        // res += min(l_max, r_max) - height[i]
        if (l_max < r_max) {
            res += l_max - height[left];
            left++;
        } else {
            res += r_max - height[right];
            right--;
        }
    }
    return res;
}

动态规划

定义left[i]表示下标i位置及其左边的最高柱子的高度，right[i]表示下标i位置及其右边的最高柱子的高度，下标i位置能接的雨水量为min(left[i],right[i])-height[i],遍历数组，计算出left[i]和right[i]，最后答案为min(left[i],right[i])-height[i]里i从0到n-1的求和总值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int trap(int[] height) {
    int n = height.length;
    int[] left = new int[n];
    int[] right = new int[n];
    left[0] = height[0];
    right[n - 1] = height[n - 1];
    for (int i = 1; i < n; ++i) {
        left[i] = Math.max(left[i - 1], height[i]);
        right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += Math.min(left[i], right[i]) - height[i];
    }
    return ans;
}

单调栈

单调栈就是保持栈内元素有序。和栈与队列：单调队列一样，需要我们自己维持顺序，没有现成的容器可以用。

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

而接雨水这道题目，我们正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。

先将下标0的柱子加入到栈中，st.push(0);。 栈中存放我们遍历过的元素，所以先将下标0加进来。

然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。

如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

int trap(int[] height){
    int size = height.length;

    if (size <= 2) return 0;

    // in the stack, we push the index of array
    // using height[] to access the real height
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);

    int sum = 0;
    for (int index = 1; index < size; index++){
        int stackTop = stack.peek();
        if (height[index] < height[stackTop]){
            stack.push(index);
        }else if (height[index] == height[stackTop]){
            // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index
            stack.pop();
            stack.push(index);
        }else{
            //pop up all lower value
            int heightAtIdx = height[index];
            while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
                int mid = stack.pop();

                if (!stack.isEmpty()){
                    int left = stack.peek();

                    int h = Math.min(height[left], height[index]) - height[mid];
                    int w = index - left - 1;
                    int hold = h * w;
                    if (hold > 0) sum += hold;
                    stackTop = stack.peek();
                }
            }
            stack.push(index);
        }
    }

    return sum;
}

最后推荐一个大佬的视频，这个大佬每次周赛都是前几名

相关文章：