如何高效解决接雨水问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何高效解决接雨水问题

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

• 哇咔咔，来打卡

[fornobugworld]

第二题建议补一下正确性证明

[syz6]

11. 盛最多水的容器 双指针算法证明
    最大容量一定位于区间 [0, n - 1]。

令 [left, right] 表示最大容量的搜索区间，res 表示当前搜索到的最大容量。

令 capacity(i, j) 表示索引为 i, j 的两条线的容量，i < j, 则 capacity(i, j) = min(height[i], height[j]) * (j - i)）。

[left, right] 初始值为最大搜索区间 [0, n - 1]。

每次循环时：
（1）比较 res 和 capacity(left, right) ，若后者较大，则将后者赋值给 res。

（2）若 height[left] < height[right]，必有 capacity(left, j) < capacity(left, right), left < j < right。因为：
a. capacity(left, j) = min(height[left], height[j]) * (j - left)

b. capacity(left, right) = min(height[left], height[right]) * (right - left) = height[left] * (right - left)

c. min(height[left], height[j]) <= height[left]

d. (j - left) < (right - left)

又 capacity(left, right) <= res，所以 capacity(left, j) < res, left < j < right。即在后面的搜索中，若有比 res 更大的容量，该更多容量对应的左界一定不是 left。所以可将搜索区间缩小为 [left + 1, right]

（3）若 height[left] >= height[right]，同（2）理可将搜索区间缩小为 [left, right - 1]

当循环结束时，搜索完了可能存在最大容量的区间，此时 res 就是最大容量。

以上证明类似两数和双指针算法的证明。

[bigyou]

第二题，如果 height[left]==height[right] 如何判断是需要移动left 还是移动right 才会出现最优解呢？

[yarkable]

@bigyou 相等的话左移右移都可以，因为中间部分的面积肯定没有这两个相等的柱子围成的面积大

[cheng-miao]

打卡

[Leochens]

接雨水js版

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {

    // 想找到第i个柱子上可以接多少雨水 res[i] 
    // 先找到右边最高的柱子max_l 找到左边最高的柱子max_r 取min(l,r)-height[i] = res[i]
    // 使用备忘录优化
    const m = height.length;
    let max_l = Array(m), max_r = Array(m);
    let res = 0, temp;
    // 初始化base case
    max_l[0] = height[0];
    max_r[m - 1] = height[m - 1];
    
    // max_l[i] 代表第i个柱子左边最大高度是多少 
    // 按照这个思路把max_l 和max_r 初始化 这块不懂可以画画这个步骤的图就懂了
    for (let i = 1; i < m; i++)
        max_l[i] = Math.max(height[i], max_l[i - 1]);
    for (let i = m - 2; i >= 0; i--)
        max_r[i] = Math.max(height[i], max_r[i + 1]);

    for (let i = 0; i < m; i++) {
        temp = Math.min(max_l[i], max_r[i]) - height[i];
        res += temp > 0 ? temp : 0;
    }

    return res;
};

[lihuagang03]

打卡，感谢楼主！

[saw008]

第一题的备忘录解法，也应该判断min(left_max, right_max)是否大于当前柱子的高度吧？假如min(left_max, right_max)是3，但当前柱子是5，直接相减得-2了，然而应当是0。

[ADSWT518]

不需要判断，因为在计算 l_max 数组的时候是取「自己高度」和「目前左边最高」的最大值，因此 l_max[i] >= height[i] 是恒成立的。r_max 同理。

[massiachan]

第一题为什么移动较矮的指针呢？好难想到。。

[ftanda-go]

好处理一点，你也可以移动右边的指针，计算复杂一些

[shiboys]

作者已经回复你了，你倒是看呀

[deepbreath373]

check in

[Hyuvo]

@saw008 审题

备忘录解法，l_max[i] 和 r_max[i] 分别代表 height[0..i] 和 height[i..end] 的最高柱子高度。

所以两个max至少是当前柱子height，所以差最小是0

[yonggui-yan]

打卡。左右两边双指针

[acmu]

听说这是 tiktok 的面试题 🤫

[Chris-zhang1]

好神奇啊，两道题都能看懂解法，但好像一下子看不出来区别

[LiuWenJia-ops]

此时的 l_max 是 left 指针左边的最高柱子，但是 r_max 并不一定是 left 指针右边最高的柱子，这真的可以得到正确答案吗？

其实这个问题要这么思考，我们只在乎 min(l_max, r_max)。对于上图的情况，我们已经知道 l_max < r_max 了，至于这个 r_max 是不是右边最大的，不重要。重要的是 height[i] 能够装的水只和较低的 l_max 之差有关

其实可以这么理解,

初始的想法是求 minmax(l_height, r_height), 但只要存在某个 r_height > l_max, 那么即使 r_height 不是 r_max, 我们也只能选择 l_max

[LiuWenJia-ops]

当存在某个 r_height == l_max 时, 也不可能取一个右边的比l_max更小的 r_height 了

[taopeng666]

第二道题这样写，可以减少计算次数
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int response = 0;
int lv_max = 0;
int rv_max = 0;
while (left < right) {
int lv = height[left];
int rv = height[right];
lv_max = Math.max(lv, lv_max);
rv_max = Math.max(rv, rv_max);
if (lv == lv_max || rv == rv_max) {
int val = Math.min(lv, rv) * (right - left);
response = val > response ? val : response;
}
if (lv > rv) {
right--;
} else if (lv < rv) {
left++;
} else if (lv == rv) {
right--;
left++;
}

    }
    return response;
}

[YuFudan]

接雨水, O(N), Python, 不需要用双指针

class Solution:
    def trap(self, height: List[int]) -> int:
        """
        一般地, 高度为h的格子, 接雨水量 = max(0, min(l_max, r_max) - h), 
        其中l_max, r_max分别为它的左右两半的最大高度.
        现找到整个数组中高度最高的地方, 分成两半.
        对于左半边, min(l_max, r_max)一定是l_max.
        因此只需顺序遍历, 维护当前看过的最高高度hmax, 若当前高度h小于它, 则可以接雨水hmax - h
        对于右半边, 可以反转一下然后当左半边处理
        """
        def calculate(arr):
            res = 0
            hmax = 0
            for h in arr:
                if h < hmax:
                    res += hmax - h
                else:
                    hmax = h
            return res
        
        i = height.index(max(height))

        return calculate(height[:i]) + calculate(height[i+1:][::-1])

[ZOULUFENG]

可以，因为本题中竖线没有宽度，所以 left 和 right 之间能够盛的水就是：
min(height[left], height[right]) * (right - left)
感觉这句话说的不够严谨。应该说至少是这些。

[syz6]

42 接雨水双指针算法，while (left < right) 语句等价于 while (left <= right) 语句。因为 left, right 一定相遇于最高柱子，即当 left == right 时，必有 height[left] == max(height[0..n - 1])。而最高柱子的接水量为 0，所以累加计算 left == right 时的最高柱子的接水量。

虽然二者效果等价，但后者更直观易懂。

[syz6]

【纠错】“所以累加计算 left == right 时的最高柱子的接水量。” 改成 “所以不必累加 left == right 时的柱子的接水量。”

[2pen]

其实双指针的循环结束条件分析，left<right和left<=right并不影响，因为最后一步一定是max-max,不能盛水的。