[暴力 | 双指针 | 单调栈] LeetCode 42. 接雨水

? “Offer 驾到，掘友接招！我正在参与2022春招打卡活动点击查看 活动详情。

42. 接雨水

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

示例 1：

输入：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 个单位的雨水（蓝色部分表示雨水）。
复制代码

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9
复制代码

提示：

• n == height.length
• 0 <= n <= 3 * 10^4
• 0 <= height[i] <= 10^5

思路一：暴力

对于第i个柱子，其左边柱子最高为l，右边柱子最高为r，则第i个柱子能接的雨水量为min(l,r) – height[i]。

遍历所有柱子，分别计算每个柱子能接到的雨水量，并求和。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0,n = height.size();
        for(int i = 1; i < n - 1; i++){
            int l = 0, r = 0;
            for(int j = i; j >= 0; j--){
                l = max(l,height[j]);
            }
            for(int j = i; j < n; j++){
                r = max(r,height[j]);
            }
            ans += min(l,r) - height[i];
        }
        return ans;
    }
};
复制代码

思路二：优化思路一,预处理出当前柱子左右两边的最高的柱子的高度值。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(),ans = 0;
        if(n == 0) return 0;
        vector<int> l(n,0),r(n,0);
        l[0] = height[0];
        for(int i = 1; i < n; i++){
            l[i] = max(height[i],l[i - 1]);
        }
        r[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i--){
            r[i] = max(height[i],r[i + 1]);
        }
        for(int i = 1; i < n - 1; i++){
            ans += min(l[i],r[i]) - height[i];
        }
        return ans;
    }
};
复制代码

思路三：双指针

• 从思路二可知，只要r_max > l_max，积水高度将由 l_max 决定，只要r_max < l_max，积水高度将由 r_max 决定;
• 所以如果一边(右边)有更高的条形块，积水的高度依赖于从左到右的高度，反之亦然。

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0,r = height.size() - 1,ans = 0;
        int l_mx = 0,r_mx = 0;
        while(l < r){
            if(height[l] < height[r]){
                if(height[l] > l_mx) l_mx = height[l];
                else ans += l_mx - height[l];
                l++;
            }else{
                if(height[r] > r_mx) r_mx = height[r];
                else ans += r_mx - height[r];
                r--;
            }
        }
        return ans;
    }
};
复制代码

思路四：单调栈

• 维护一个单调递减栈,当有元素需要弹出时,说明已经形成了低洼,此时计算当前的低洼的高度并累加到结果中即可。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, n = height.size();
        if(n == 0) return 0;
        stack<int> st;
        for(int i = 0; i < n; i++){
            while(st.size() and height[st.top()] < height[i]){
                int cur = st.top();
                st.pop();
                if(st.size()) ans += (i - st.top() - 1) * (min(height[i],height[st.top()]) - height[cur]);   
            }
            st.push(i);
        }
        return ans;
    }
};
复制代码