42. 接雨水

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

接雨水

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

示例:

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

输出: 6

Solution1（直观解法）:

我们可以稍稍使用减法，接水的区域正好是最好的柱子乘以整个宽度，再减去从左到制高点和从右到制高点每个单调上升的柱子到两边的距离乘以前柱子的高度差。

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
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        //小于等于两个是蓄不住水的。
        if(n <= 2) return 0;
        int ans = 0;
        int Max = -1;
        int k = -1;
        //找到至高点。
        for(int i = 0; i < n; i++){
            //先减去柱子本身高度
            ans -= height[i];
            if(Max < height[i]) Max = height[i], k = i;
        }
        //加上整个图的面积
        ans += n*Max;
        
        //从前到最高点，每次减去从开始到每个更高柱子高度的面积。
        int cur = height[0];
        int i = 1;
        while(i <= k){
            //i为从开始到当前柱子距离。height[i]-cur为高度差。
            if(height[i] > cur) ans -= i * (height[i]-cur),cur = height[i];
            i++;
        }
        cur = height[n-1];
        i = height.size()-2;
        while(i>=k){
            //i最后到当前柱子的距离。height[i]-cur为高度差。
            if(height[i] > cur) ans -= (n-i-1) * (height[i]-cur),cur = height[i];
            i--;
        }
        return ans;
    }
};

Solution2（单调栈）：

使用单调栈的原因是我们发现如果把每个柱子当作最低点，则接雨水的区域是左右第一个比当前柱子高的柱子所形成的区域乘以两者之间较小的柱子与当前柱子的高度差。所以我们进行单调栈寻找左右最近的比当前元素高的位置，来计算结果。

从直观来看，这样很像一层层的往里接水。（当然计算的时候不一定只是一层）

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();
        stack<int> s;
        int ans = 0;
        for(int i = 0; i < n; i++){
            //找每个元素右边最近的大于他的值。//单调递减栈
            while(s.size() && height[i] > height[s.top()]){
                int top = s.top();
                s.pop();
                if(s.empty())break;
                //由于维持的是单调递减栈，所以当前栈顶是目前已知的最小一个元素，将栈顶取出，而新的栈顶元素与新发现的比它大的元素，一定能就组成边界，使得以目前最小元素为底，至左右边界中小的那一个，可以接到雨水。形象点就是一层一层的接。
                int dis = i-s.top()-1;
                ans += dis * (min(height[i],height[s.top()])-height[top]);
            }
            s.push(i);
        }
        return ans;
    }
};

Solution3（双指针）：

我们写第一种解法时发现，并没有必要去进行那么多减法，每次直接观察当前柱子高度与之前记录的最高柱子的高度关系，如果没有之前最高柱子高就说明可以接住雨水（因为我们每次寻找的是更高的柱子，直到全图最高柱子出现为止），这样可以直接计算该柱子之上可以接住的雨水。由于左右都是到了最高柱子就会停止，所以使用双指针来优化，每次选较小的柱子来计算，直到制高点。

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
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n-1;
        int lm = -1,rm = -1;
        int ans = 0;
        while(l < r){
            //从小的一方开始
            if(height[l] < height[r]){
                if(height[l] > lm){
                    lm = height[l];
                }else{
                    ans += lm-height[l];
                }
                l++;
            }else{
                if(height[r] > rm){
                    rm = height[r];
                }else{
                    ans += rm-height[r];
                }
                r--;
            }
        }
        return ans;
    }
};