T42

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

示例 1：img

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

这是之前被某公司带火的T42接雨水。我没什么奇思妙想，也看不出什么深刻的规律。我能看到的只是一个普通人能看到的世界。因此，站在大众肯定能看得懂的角度，朴素的去解答一个问题。

既然我们要计算积水的总量，我们可以这样思考：每个竖直格子中的积水总量是多少？观察整个图景，一些地方是有积水的，而一些地方则是柱子本身。

我们可以将数轴划分为以 [0,1], [1,2], [2,3], …, [n-2,n-1] 的形式，然后画竖直线。这样，积水的总量就是每个竖直格子中积水量的总和。

那么，每个竖直格子能容纳多少积水？显然，这取决于格子内柱子的高度。

那么，如果没有柱子，这个格子能容纳的积水量取决于什么？取决于它左右两侧的柱子的高度。具体来说，取决于它左右两侧分别的最高柱子中，高度较小的那一个。

因此，我们需要计算每个位置左右两侧的最高柱子高度，然后较矮的那个高度就是没有柱子的情况下，能容纳的水量。将这个值存入数组，再减去当前位置柱子的高度，就是实际的积水量。把所有位置的积水量加起来，就得到了最终的结果。

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
30
31
32
fun trap(height: IntArray): Int {
        val n = height.size
        val memoLeft = IntArray(n) { 0 }
        var curML = 0  
  			//计算左侧最大高度
        for (i in 1 until n) {
            curML = max(curML, height[i - 1])
            memoLeft[i] = curML
        }
    
        val memoRight = IntArray(n) { 0 }
        var curMR = 0

        // 计算右侧最大高度
        for (i in n - 2 downTo 0) {
            curMR = max(curMR, height[i + 1])
            memoRight[i] = curMR
        }

        var sum = 0

        // 计算总和
        for (i in height.indices) {
            val minHeight = min(memoRight[i], memoLeft[i])
            if (minHeight > height[i]) {
                sum += minHeight - height[i]
            }
        }

        return sum
        }
}