接雨水

问题描述

给定 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 个单位的雨水（蓝色部分表示雨水）。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路 1：双指针

• 设置两个变量分别记录左右最高高度；

• 双指针移动时优先移动较矮的位置，并更新能带来的增量；

• 画图理解这个过程；

Python

class Solution:
    def trap(self, height: List[int]) -> int:

        l, r = 0, len(height) - 1  # 首尾双指针
        l_max, r_max = 0, 0  # 记录当前位置，左右的最高高度
        ret = 0
        while l < r:
            # 更新左右最高高度
            l_max = max(l_max, height[l])
            r_max = max(r_max, height[r])

            # 取左右较矮的作为当前位置
            if height[l] < height[r]:  # <= 也可以
                cur = height[l]
                l += 1
            else:
                cur = height[r]
                r -= 1
            
            ret += min(l_max, r_max) - cur  # 更新当前位置能带来的增量
        
        return ret

思路 2：遍历两次

• 分别从左向右和从右向左遍历两次，记录每个位置左右两侧的最高高度；

C++

class Solution {
public:
    int trap(vector<int>& H) {
        int n = H.size();
        
        vector<int> l_max(H);
        vector<int> r_max(H);
        
        for(int i=1; i<n; i++)
            l_max[i] = max(l_max[i-1], l_max[i]);
        
        for(int i=n-2; i>=0; i--)
            r_max[i] = max(r_max[i+1], r_max[i]);
        
        int ret = 0;
        for (int i=1; i<n-1; i++)
            ret += min(l_max[i], r_max[i]) - H[i];
        
        return ret;
    }
};