0042. 接雨水

[utterances-bot]

0042. 接雨水 | 算法通关手册

42. 接雨水 # 标签：栈、数组、双指针、动态规划、单调栈 难度：困难 题目大意 # 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，用数组 height 表示，其中 height[i] 表

https://algo.itcharge.cn/Solutions/0001-0099/trapping-rain-water/

[S1mpleBug]

附C++代码

附上动态规划的解法，左右数组leftMax、rightMax分别的第i位存放的是当前i之前最大的高度，和i之后最大的高度。根据高度，最后选取每次当前位置i左右的最小高度，计算是否能盛入雨水。

const int N = 2e4+5;
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int leftMax[N] = {0};
        int rightMax[N] = {0};

        for(int i = 1; i < n-1; ++i)
            leftMax[i] = leftMax[i-1] > height[i-1] ? leftMax[i-1] : height[i-1];
        for(int i = n-2; i > 0; --i)
            rightMax[i] = rightMax[i+1] > height[i+1] ? rightMax[i+1] : height[i+1];
        int res = 0, minheight;
        for(int i = 1; i < n-1; ++i) {
            minheight = leftMax[i] <= rightMax[i] ? leftMax[i] : rightMax[i];
            if(minheight > height[i]) res += (minheight-height[i]);
        }
        return res;
    }
};

[Therm4l]

附C++代码，使用的最简单的双指针方法，方法为 盛最多水的容器 接雨水

class Solution {
public:
    int trap(vector<int> &height) {
        int ans = 0;
        int l = 0, r = height.size() - 1;
        int pre_max = 0, suf_max = 0;
        while(l <= r){
            pre_max = max(pre_max, height[l]);
            suf_max = max(suf_max, height[r]);
            if(pre_max < suf_max){
                ans += pre_max - height[l];
                l++;
            }
            else{
                ans += suf_max - height[r];
                r--;
            }
        }
        return ans;
    }
};

方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

[edzq]

感觉这题用Stack稍微有点绕....算面积需要对单调栈出入栈的性质理解非常透彻...@S1mpleBug的动态规划计算每个index的left max和right max的思路更好理解，并且可以算是从暴力解法过渡到动态规划。
暴力解法：

class Solution:
    def trap(self, height: List[int]) -> int:
        # brute force: for each bin, find the left max, right max, and using the min max to minus current hight
        # TC is O(N^2)
        res = 0
        n = len(height)
        for i in range(n):
            l_max, r_max = 0, 0
            # l_max, find the max value[0, i]
            for j in range(i, -1, -1):
                l_max = max(l_max, height[j])
            # r_max: find max value in [i,n-1]
            for j in range(i, n):
                r_max = max(r_max, height[j])
            res += min(l_max, r_max) - height[i]
        return res

因为对每个元素都用到了lleft max和right max, 所以可以先存下来。即bottom up的思路，分别从右到左和左到右，记录每个子数组的最大值，然后更新下一个更大的子数组的最大值.

class Solution:
    def trap(self, height: List[int]) -> int:
        # DP to store the l_max and r_max for each index
        # iterately accumulate the rain: min(l_max[i], r_max[i]) - height[i]
        n = len(height)
        l_max = [0] * n
        l_max[0] = height[0]
        r_max = [0] * n
        r_max[-1] = height[-1]
        # l_max
        for i in range(1, n):
            l_max[i] = max(l_max[i-1], height[i])
        # r_max
        for i in range(n - 2, -1, -1):
            r_max[i] = max(r_max[i+1], height[i]) 
        res = 0
        for i in range(n):
            res += min(l_max[i], r_max[i]) - height[i]
        return res