Ricky.L的随笔
0%

LeetCode.42.接雨水（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.42.接雨水（困难）

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

题解

解法1：动态规划，O(n)空间复杂度

拆分问题

所有的积水由每一列的积水量累加得来。

某一列的积水量由什么决定？

  1. 先要看左右两边最高的柱子有多高，这决定了当前列能积多高的水，并且最多只能积到较矮的那个柱子的高度，否则水会溢出。
  2. 这个高度减去当前柱子高度，就是当前列可以积的水量。

第i列的积水量求解公式

第i列的积水量 = min(0到i - 1列中最高的柱子的高度, i + 1列到n - 1列中最高柱子的高度) - 当前列柱子高度

所以要把每一列左边和右边最高的柱子先求出来。

第i列左边的最高的柱子怎么找？

从0到i - 1遍历一遍height数组，找最大的。
实际可以从左到右遍历一遍height数组，把前面记录的最大的柱子高度跟第i - 1个柱子高度比较，取较大值就行了。

第i列右边的最高的柱子的高度怎么找？

从右向左遍历一遍height数组，把前面记录的最大的柱子高度跟第i + 1个柱子高度做对比，取较大的。

边界情况

第1个柱子左边没有柱子，其左边最高柱子高度是0，也无法积水。
最后1个柱子右边没有柱子，其右边最高柱子高度是0，也无法积水。

代码（kotlin）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    fun trap(height: IntArray): Int {
        val n = height.size
        val maxLeft = IntArray(n) { 0 }
        val maxRight = IntArray(n) { 0 }
        for (i in 1 until n) {
            maxLeft[i] = maxOf(maxLeft[i - 1], height[i - 1])
        }
        for (i in (n - 2) downTo 0) {
            maxRight[i] = maxOf(maxRight[i + 1], height[i + 1])
        }
        var water = 0
        for (i in 1..(n - 2)) {
            val h = maxOf(maxLeft[i], maxRight[i])
            if (h > height[i]) {
                water += h - height[i]
            }
        }
        return water
    }
}

时间复杂度： O(n)
空间复杂度： O(n)

解法2：动态规划，O(1)空间复杂度

空间优化

求每一列的积水的时候，maxLeft[i]和maxRight[i]只用到了一次，后续不会再查询之前的值，所以可以用两个变量leftMax、rightMax代替数组。

怎么用leftMax代替maxLeft数组？

maxLeft数组是从左到右遍历数组height求得的，在从左到右遍历height数组求第i列积水量的时候，就可以顺便计算出第i个柱子左边最高的柱子的高度，即leftMax。

怎么用rightMax代替maxRight数组？

maxRight数组是从右到左遍历数组height求得的，想办法能想办法能从右到左遍历数组就行了。

什么时候应该从右到左遍历？什么时候从左到右？

当左侧的柱子高度比右侧柱子高，需要看较矮的右侧的柱子高度，才能决定某一列能积多少水，左边不管多高都不会决定能积多少水，此时应该从右到左遍历。
直到右侧柱子比左侧柱子高，才需要从左边到右边检查。

初始情况是怎样的？怎么开始？

第一列左边没有柱子，无法积水。
最后一列右边没有柱子，无法积水。
计算积水只考虑区间[1, n - 2]。
可以直接令：
leftMax = height[0]
rightMax = height[n - 1]

具体怎么判断决定height数组的遍历方向？

  1. 如果发现左边柱子比右边矮，即leftMax < rightMax，可以先计算左边的积水，随后如果发现当前柱子高度比leftMax高，再更新leftMax。
  2. 如果发现右边柱子比左边矮，即leftMax > rightMax，先计算右边的积水，随后如果发现当前柱子高度比rightMax高，再更新rightMax。

代码

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
class Solution {
    fun trap(height: IntArray): Int {
        val n = height.size
        if (n <= 2) return 0
        var leftMax = height[0]
        var rightMax = height[n - 1]
        var water = 0
        var left = 1
        var right = n - 2
        // 要计算区间[1, n - 2]中所有列的积水情况，所以边界条件要包含left == right的情况，才能包含所有的情况
        while (left <= right) {
            if (leftMax < rightMax) {
                if (leftMax > height[left]) {
                    water += leftMax - height[left]
                }
                leftMax = maxOf(leftMax, height[left])
                left++
            } else {
                if (rightMax > height[right]) {
                    water += rightMax - height[right]
                }
                rightMax = maxOf(rightMax, height[right])
                right--
            }
        }
        return water
    }
}

时间复杂度： O(n)
空间复杂度： O(1)

解法3：直观模拟 -> 单调栈

梳理

要能积水，需要多根柱子形成凹槽。

如何判断形成了凹槽？

朝一个方向依次看柱子高低，是否能形成高、低、高的排列。
在已经形成下坡的情况下，一旦发现出现了上坡，就形成了凹槽，就可以计算积水量了。
如果发现上坡，但是前面没有下坡，无法积水。

如何计算凹槽的积水量

穷举出凹槽的所有可能情况，逐个分析，再归纳。
从最基本的情况看起，再添加有限的步骤，推导出更复杂的情况。

基本情况

一个凹槽最少也要3个柱子，假设3个柱子从左到右依次叫L、M、R，高度排列依次是高、低、高。
凹槽积水量 = minOf(L高度, R高度) - M高度

如果有多个相同高度的M，计算方式会怎么变化？

就变成求矩形面积了：
凹槽积水量 = (minOf(L高度, R高度) - M高度) * L到R的距离
L到R的距离 = R索引 - L索引 - 1

如果有4个不同高度的柱子（多一个柱子）形成的凹槽，计算方式会怎么变化？

因为是从左到右看柱子高度的，一旦发现上坡就触发计算，所以可以先看下坡中柱子多的情况，比如：[3,2,1,4]。

1
2
3
4
5
6
7
             #   
       # a b #
       # # c #
       # # # #
index: 0 1 2 3

#表示柱子，小写字母表示积水区域

此时积水面积不是矩形，左下方是一个阶梯型。
如果按之前的办法求解，从3依次回看2、1，会检测到凹槽形成，可以求得c的面积。
积水面积剩下a、b，可以发现刚好是一个矩形，面积为(minOf(3高度, 2高度) - 1高度) * 1到3的距离。
如果左边还有更高的柱子，会形成新的矩形，还是一样的计算过程。

计算规律

这种阶梯形状的积水面积，可以按行拆分为不同的矩形，先求下面的矩形面积，再求上面的矩形面积，最后累加。

然后再看右边柱子多的情况，得看右边形成新的凹槽才有讨论意义，那就是看一下有两个凹槽的情况会怎样。

有两个凹槽时，计算方式会怎样变化？

1
2
3
4
5
6
                   #
       # b b b b b #
       # a a # b b #
       # # a # b b #
       # # # # # # #
index: 0 1 2 3 4 5 6

可以发现0到3的第一个凹槽中第0个最高的柱子会影响到4到6的第二个凹槽的积水面积的计算。
第一个凹槽积水量计算过后，1和2两个柱子对于第二个凹槽积水面积计算没有影响了。
在计算新凹槽积水量的时候，需要读取以前比较高的柱子高度，太低的柱子就可以忽略了。

怎么获取和存储计算积水量需要的信息？

每个矩形面积的计算，是在发现有上坡后开始的，检测上坡就是需要知道当前柱子高度和前一个柱子高度，这个在遍历height数组时可以直接获取。

发现上坡后，需要知道：

  1. 前面有没有形成下坡的柱子
  2. 柱子之间的距离
  3. 柱子的高度

柱子距离必须要记录柱子索引位置；
形成下坡意思就是柱子高度要单调递减；
柱子高度可以根据柱子索引查询height数组；
访问下坡中柱子还要从右到左依次访问。

我们遍历检查的顺序是从左到右，访问顺序反过来，符合这个特点的数据结构就是栈。
入栈时保存的是柱子索引。
栈内柱子保持高度单调递减，不存储递增的柱子，因为对于后续计算积水没有意义。
当前柱子前面一个柱子也算下坡中，也存储在栈中，方便统一处理。
判断前面有没有形成下坡，就判断栈是否不为空。

代码（kotlin）

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
import java.util.*

class Solution {
    fun trap(height: IntArray): Int {
        // 栈存储形成下坡的柱子
        val stack = ArrayDeque<Int>()
        var water = 0
        for (i in height.indices) {
            // 之前有下坡，现在发现上坡，形成凹槽了，可以计算积水面积了
            // 凹槽积水面积可能是阶梯形，所以要不停的读取前面下坡中的柱子计算矩形积水面积，这里需要一个循环
            while (stack.isNotEmpty() && height[stack.peek()] < height[i]) {
                // 前面凹槽中高度低的柱子要出栈，因为其对于后面凹槽的计算没有意义
                val cur = stack.pop()
                // 相同高度的柱子会形成矩形面积的积水，一起计算积水量
                while (stack.isNotEmpty() && height[stack.peek()] == height[cur]) {
                    stack.pop()
                }
                // 前面有下坡，才能形成凹槽，计算积水才有意义，所以要对栈判空，有可能之前栈里只存储了一个柱子
                if (stack.isNotEmpty()) {
                    // 现在栈顶的柱子高度是大于curHeight的，形成凹槽了
                    val h = minOf(height[stack.peek()], height[i]) - height[cur]
                    val w = i - stack.peek() - 1
                    water += w * h
                }
            }      
            stack.push(i)
        }
        return water
    }
}

解法4：数学拆解 -> O(1)空间复杂度

从图形上看积水区域特点

1
2
3
4
        b  b  b  b  b  #  a  a  #  c  c  c  c  c
        b  b  #  a  a  #  a  a  #  a  #  c  c  c
        #  a  #  a  a  #  a  a  #  a  #  a  #  c
index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13

观察得知：
区间矩形面积 = a的面积 + #的面积 + b的面积 + c的面积

区间矩形面积已知。
区间矩形面积 = 区间宽度 * 最高柱子高度

#的面积已知。
#的面积 = 所有柱子高度的和

有没有办法知道b和c的面积？
b和c是阶梯状的，不好单独计算。
可以看其处于哪个好计算的部分，再看能不能把b和c的面积拆解出来。

  1. 如果从左到右遍历height数组，是可以知道 #的面积 + a的面积 + c的面积，遇到比之前高的柱子就一直累加高柱子的高度就行了，假设这个面积为left。
  2. 如果从右到左遍历height数组，是可以知道 #的面积 + a的面积 + b的面积，也是遇到比之前高的柱子就一直累加高柱子的高度就行了，假设这个面积为right。

left + right = #的面积 + a的面积 + (#的面积 + a的面积 + b的面积 + c的面积)
化简得：
left + right = #的面积 + a的面积 + 区间矩形面积
可得：
a的面积 = left + right - #的面积 - 区间矩形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun trap(height: IntArray): Int {
        val n = height.size
        var left = 0
        var right = 0

        var maxHeight = 0
        for (i in 0 until n) {
            maxHeight = maxOf(maxHeight, height[i])
            left += maxHeight
        }

        maxHeight = 0
        for (i in n - 1 downTo 0) {
            maxHeight = maxOf(maxHeight, height[i])
            right += maxHeight
        }

        val rectArea = n * maxHeight
        val pillarArea = height.sum()
        
        return left + right - rectArea - pillarArea
    }
}