fucking-algorithm 如何高效解决接雨水问题

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

Open utterances-bot opened this issue 3 years ago • 10 comments

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

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

Jan 29 '22 06:01 utterances-bot

哇咔咔，来打卡

Jan 29 '22 06:01 deepbreath373

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

Feb 17 '22 13:02 fornobugworld

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

Mar 02 '22 04:03 bigyou

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

Apr 16 '22 14:04 yarkable

打卡

Apr 26 '22 07:04 cheng-miao

接雨水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;
};