题目描述

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

示例如图：

样例

示例 1：
lc42_1

1
2
3
4
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

算法1

(线性扫描三次) $O(n)$

对于每一个柱子来说，若他要能够接住雨水，那么必须满足在这根柱子的左右两边存在着高度高于他的其他柱子，这样才有可能形成凹槽接住雨水。

那么可以通过两次遍历整个数组，第一次遍历存储每个位置左侧的最高柱子，第二次遍历存储每个位置右侧的最高柱子

最终，预处理完左右两侧的柱子之后，我们可以最后遍历所有的柱子，根据每个柱子左右两侧的最大柱子计算以该柱子之上可以接住的雨水即可

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left_max(n), right_max(n);

        left_max[0] = height[0], right_max[n - 1] = height[n - 1];

        for(int i = 1; i < n; i ++)
            left_max[i] = max(left_max[i - 1], height[i]); // 预处理左侧最高柱子

        for(int i = n - 2; i >= 0; i --)
            right_max[i] = max(right_max[i + 1], height[i]); // 预处理右侧最高柱子

        int res = 0;
        for(int i = 0; i < n; i ++)
            res += min(left_max[i], right_max[i]) - height[i];

        return res;
    }
};

对于与这种方法来说，思路比较容易理解，但是借助了额外 $O(n)$ 的空间，并且遍历了三遍数组，可以进行进一步的优化

算法2

(利用单调栈来优化) $O(n)$

可以考虑使用一个单调递减的单调栈来维护每一个柱子左侧柱子的信息。

可以这么考虑： 当前的柱子若要接住雨水，他必须与右侧、左侧比他高的柱子形成凹槽， 那么我们使用一个单调递减的栈，每次遇到一个新柱子时，将现在栈顶的柱子高度与即将入栈的新柱子进行对比，可以有如下情况

  1. 如果当前的遇到的新柱子高度 高于 当前栈顶柱子的高度， 说明有可能会形成凹槽，此时应当将栈顶的柱子弹出，作为凹槽的底部计算面积， 记为 top
  2. 如果弹出 top 后，当前栈仍然不为空，说明以 top 为底的凹槽左边仍然存在着较高的柱子，那么可以形成一个完整的槽， 此时可以接雨水的量就可以使用三者的高度、横坐标来计算了
  3. 如果弹出 top 后，栈空，说明此时这个凹槽缺了口，不能接雨水，不考虑这种情况

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk;
        int n = height.size();

        int res = 0;
        for(int i = 0; i < n;  i++)
        {
            while( stk.size() && height[i] > height[stk.top()])
            {
                int top = stk.top();
                stk.pop();
                if( stk.empty()) break;
                res += (min(height[stk.top()], height[i]) - height[top]) * (i - stk.top() - 1);
            }
            stk.push(i);
        }

        return res;
    }
};

然而，单调栈的思路虽然很巧妙，但是不容易想到，同时仍然使用了额外 $O(n)$ 的空间，因此考虑另外的方法来进行空间上的优化

算法3

(利用双指针来优化) $O(n)$

由第一种算法启发，我们可以考虑不使用额外的数组来存储每个柱子左右两端的更高柱，转而考虑使用两个指针来维护相应的信息，那么空间将会优化至 O(1)

初始时，指定两个指针分别指向数组的开头和末尾，每次比较两个指针所指的柱子高度。若要接住雨水的话，必然是较小者更能形成凹槽，因此每次取其中较小者作为凹槽的底，计算当前这个短柱子上方可以放多少水，能够存放的水量就是当前左侧最高柱子与当前指向的最低柱子之差。两指针分别向右、向左遍历数组，相遇后停止，可以达到 O(n) 的时间复杂度以及 O(1) 的空间复杂度

C++ 代码

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 {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int l_max = height[0], r_max = height[n - 1];

        int res = 0;
        while( l <= r)
        {
            if( l_max < r_max)
            {
                res += max(0, l_max - height[l]);
                l_max = max(l_max, height[l]);
                l ++;
            }
            else
            {
                res += max(0, r_max - height[r]);
                r_max = max(r_max, height[r]);
                r --;
            }
        }

        return res;
    }
};