经典算法题 - 接雨水

前言

经济萧条导致了移动端开发岗的减少，进而使得研发人员的竞争尤其激烈。算法，成为了面试大厂的必备条件。

知识点

• 双指针、动态规划

描述

• 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
• 

示例1

• 输入：[3， 1， 2， 5， 2， 4]
• 输出：5
• 说明：如上图，数组 [3， 1， 2， 5， 2， 4] 表示柱子高度，这种情况下可以接5个单位的雨水，图中蓝色部分。

示例2

• 输入：[4, 5, 1, 3, 2]
• 输出：2

思路

• 这是典型的双针对问题。左指针指向左边，右指针指向右边。
• 计算每一列可以存储的水量，这必然要有一个最值，减去当前格子的存水量，这个存水量最后要累加。
• 如果左指针小，右指针向右移动，否则右指针向左移动，直到两指针相邻或相遇

代码

/**
 * 接雨水问题
 */
function solution(arr) {
    // 双指针，一左一右
    let l = 0;
    let r = arr.length - 1;
    // 左右的最值
    let maxL = 0;
    let maxR = 0;
    // 结果
    let res = 0;
    while (l < r) {
        // 左边的小
        if (arr[l] < arr[r]) {
            // 比最值小则需要累加存水量
            if (arr[l] < maxL) {
                res += maxL - arr[l];
            } else {
                // 否则替换最值
                maxL = arr[l];
            }
            // 左边的小则左指针向右移动
            l++;
        } else {
            // 右边同理
            if (arr[r] < maxR) {
                res += maxR - arr[r];
            } else {
                maxR = arr[r];
            }
            r--;
        }
    }
    return res;
}

总结

• 接雨水问题是字节最爱问的题，说是难度为困难，但其实根本达不到困难的级别
• 掌握好双指针的思路，其实很好解。