JS_LeetCode07：接雨水

image-20250515003745597

7.接雨水

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

双指针

好难，想了好久。T T

image-20250515001511472

首先，接雨水问题细化为每一个单位能存放的雨水，而每个单位的雨水容量取决于：

左方向最高的柱子高度、右方向最高的柱子高度、自身柱子高度

这个很关键！如果左方向和右方向的最高柱子高度比自身柱子高，能够蓄水，并且蓄水的容量为左右方向的最高柱子中的较矮柱子高度减去自身柱子高度；否则，不能够蓄水。

那我们就想，遍历每一个单位，去寻找它的左右方向的最高柱子。这很暴力。

直接在两端设置指针，它们的指向代表准备计算的单位容量。关注其中较矮的柱子，因为另外一边的柱子已经比它高了，那么另外一边挡住了水，能不能装得下就取决于这一边的最高柱子和自身高度。如果自身高度比这一边的最高柱子高，就不能蓄水，并且更新这一边的最高柱子，否则，可以蓄水，计算水容量。最后移动这一边的指针继续向中间前进。直到双指针相遇。

整个过程需要关注短柱子在哪一边！是更新最大高度还是蓄水！移动指针！

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let left = 0
    let right = height.length  - 1
    sum_water = 0
    let leftMax = 0
    let rightMax = 0
    while (left < right){
      if (height[left] < height[right]){
        if (height[left] < leftMax) {
            sum_water += leftMax - height[left]
        }else {
            leftMax = height[left]
        }
        left ++
      }else {
        if (height[right] < rightMax) {
            sum_water += rightMax - height[right]
        }else {
            rightMax = height[right]
        }
        right --
      }
    }
    return sum_water
};