42. Trapping Rain Water

Leetcode link

题目简介

/**
 * @param {number[]} height
 * @return {number}
 */

题目给我们一个数字数组 height 表示连续柱子的高度

要求我们求出，这些柱子最多能装多少体积的水

解题思路

核心思路：任意一个柱子上方能装多少水取决于其左右两边各自最高柱子中比较低的柱子与当前柱子高度的差

举个例子：

有一个 height 为 [1, 0, 10]，其中下标为 1 的柱子最多能装 1 单位的水（其左边最高柱子高度为 1，右边最高柱子高度为 10，其中左边柱子比较低，所以用左边柱子高度减去当前柱子高度，也就是 1-0=1）

我们把这个思想带到题目中，我们需要两个指针 left，right 分别指向当前的最左与最右元素

以及两个指针 leftMax 与 rightMax 分别记录两边最高的柱子

每次操作中，我们需要把高度较低的指针往中间移一格：

• 如果当前的柱子高度比原来的低，则我们记录高度差
• 如果当前的柱子高度比原来的高，我们更新 leftMax 或 rightMax

我们持续上述操作直到 left >= right 则循环终止，此时返回我们所有记录的高度差之和即为答案

Javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let left = 0
    let right = height.length - 1
    let leftMax = height[left]
    let rightMax = height[right]
    let res = 0

    while(left < right) {
        if(height[left] < height[right]) {
            left++
            leftMax = Math.max(height[left], leftMax)
            res += leftMax - height[left]
        } else {
            right--
            rightMax = Math.max(height[right], rightMax)
            res += rightMax - height[right]
        }
    }
    return res
};