接雨水

last modify

问题描述

给定 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;
    }
};

Last updated