VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 42. 接雨水

Posted on Edited on In , ,

摘要：
很容易就联想到使用栈来解决。

题目

给定 $n$ 个非负整数表示每个宽度为 $1$ 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
pic0x0

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例：

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

按列计算（动态规划计算最值）

遍历每列，判断要不要计算列上的积水。
如何判断？计算出该列左侧最高列高度，计算右侧最高列高度。
若该列比二者都小，则该列需要计算;否则不需计算。
如何分别计算某列两侧最值？
可维护两个数组分别存储每列左右两侧最值。

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
class Solution {
    /*
     * [列解法, 动态规划]
     * 1ms
     * 39.3MB
     */
    public int trap(int[] height) {
        int res = 0;
        int len = height.length;
        int[] leftSideMax = new int[len];
        int[] rightSideMax = new int[len];
        //第一列和最后一列不需要计算两侧最值
        for (int i = 1; i < len - 1; i++) {
            leftSideMax[i] = Math.max(leftSideMax[i - 1], height[i - 1]);
        }
        for (int i = len - 2; i > 0; i--) {
            rightSideMax[i] = Math.max(rightSideMax[i + 1], height[i + 1]);
        }
        for (int j = 1; j < len - 1; j++) {
            int minimum = Math.min(leftSideMax[j], rightSideMax[j]);
            if (height[j] < minimum) {
                res += (minimum - height[j]);
            }
        }
        return res;
    }
}

单调栈

核心思想是先降后增必有积水。
这个就有点像有效括号，一对儿。
维护一个单调递减的栈，栈中存入柱子下标。（为什么存入下标而不直接存入高度？因为我们可能会计算两个相隔若干柱子之间的距离。）
入栈：栈为空时；当前柱子低于栈顶柱子。
出栈：当前柱子高于栈顶柱子。

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
42
43
44
45
/*
 * 2021-6-23 23:13:08
 * @Author: etoa
 */
static const auto shutdown = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();

class Solution {
public:
    static constexpr int N = 30010;
    pair<int, int> stk[N];  // idx - height
    int tt = 0;
    int len;
    int res = 0;

    int trap(vector<int>& height) {
        this->len = height.size();

        for (int i = 0; i < len; i++) {
            if (!tt || height[i] <= stk[tt].second) {
                stk[++tt] = {i, height[i]};
                continue;
            }
            // 当前高度高于栈顶，可能会蓄水
            // 要从栈顶向下找到一个大于栈顶的柱子，如果存在则一定会蓄水，不存在则一定不会蓄水
            for (; tt && height[i] > stk[tt].second;) {   // 栈内可能有多个柱子和当前柱子构成蓄水条件
                int stk_top_height = stk[tt].second;
                for (; tt; --tt) {
                    if (stk[tt].second > stk_top_height) {  // 找到了
                        int l = stk[tt].first, r = i;
                        int lheight = stk[tt].second, rheight = height[i];
                        res += (r - l - 1) * (min(lheight, rheight) - stk_top_height);
                        break;
                    }
                }
                // 栈顶自动更新
            }
            // 栈内已无柱子和当前柱子构成蓄水条件
            stk[++tt] = {i, height[i]}; // 不管之前找没找到，都将当前柱子入栈; 此时栈可能为空（之前没找到），也可能非空，之前找到了
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    /* 单调栈 简化代码
     * 4ms - 29.81%
     * 39.5MB, 11.78%
     */
    public int trap(int[] height) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        int len = height.length;
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) { //有可能可计算体积
                int heightInfoBeforePop = stack.peek();
                stack.pop(); // 当前柱子高于栈顶柱子时，出栈。记得出栈前先保存栈高数据。
                if (stack.isEmpty()) break; //不可计算体积
                else {
                    int stackTop = stack.peek();
                    res += ((i - stackTop - 1) * (Math.min(height[i], height[stackTop]) - height[heightInfoBeforePop]));
                }
            }
            stack.push(i); // 栈空或当前柱子小于等于于栈顶柱子高度时，入栈
        }
        return res;
    }
}

原题链接： LeetCode 42. 接雨水