42. 接雨水

42. 接雨水

力扣题目链接[1]

给定 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 个单位的雨水（蓝色部分表示雨水）。

「提示：」

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

思路：

本题可以使用动态规划、单调栈、双指针求解。这次采用双指针法。

首先明确几个变量的含义：

left_max：左边的最大值，它是从左往右遍历找到的
right_max：右边的最大值，它是从右往左遍历找到的
left：从左往右处理的当前下标
right：从右往左处理的当前下标

定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。

定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。

定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max < right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。所以当left_max < right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

上述思路参考自官方题解，下面说说个人的看法。

能接多少雨水，取决于低洼左右的较低高度的柱子。可以理解为就是所谓的木桶理论。因此通过左右指针，分别找到左边的最大值和右边的最大值。然后比较哪个最大值较小，就以哪个为基准计算更低处与其的差值，然后累加到最终结果中。因为这里计算的是垂直方向的差值，因此不需要做额外的处理。

双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let total = 0;
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    while (left <= right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) {
        total += leftMax - height[left];
        left++;
        } else {
        total += rightMax - height[right];
        right--;
    }
  }
  return total;
};

总结

本题有多种解法，这里采用双指针求解。如果采用动态规划，那么就需要找到动态规划方程然后再进行求解。双指针通过找到柱子的短板，进而求得每个柱子在垂直方向的差值，直到双指针相遇，求出的累加和就是最后的结果。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/problems/trapping-rain-water/