【算法小记】接雨水的不同解法

题目连接：https://leetcode.cn/problems/trapping-rain-water/

1、暴力解法

首先最容易想到的是暴力解法，对每一列进行遍历，去找到它左边最高的柱子和右边最高的柱子，然后用这两个高度中最小的值去和当前柱子高度比较，如果大于当前高度，那么作差，就是当前位置可以接到的雨水高度了。具体见代码和注释。
PS：双重循环，时间复杂度是O(n)，leetcode现在跑会超时！！！

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        # 存放总的雨水量
        res = 0
        # 特判，如果柱子的个数少于3，那不可能接到水
        if n<3:
            return 0
        # 因为两个边界的柱子不能接到水，所以只考虑从1到n-2
        for i in range(1,n-1):
            # 找到左边最高的柱子
            max_left = 0
            for j in range(i-1,-1,-1):
                if height[j]>max_left:
                    max_left = height[j]
            # 找到右边最高的柱子
            max_right = 0
            for j in range(i+1,n):
                if height[j]>max_right:
                    max_right = height[j]
            # 短板效应，装水量取决于矮的那个
            min_h = min(max_left,max_right)
            # 只有当左右柱子中矮的那个比当前高度高，才能接到水
            if min_h>height[i]:
                res += min_h-height[i]
        return res
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

2.动态规划

因为解法一中，对每个柱子的左右最高柱子都遍历去求了一遍，所以我们提出用备忘录的形式优化一下。比如我们可以用两个数组max_left和max_right分别来保存记录索引为i的柱子左右最高柱子的高度。
max_left[i] = max(max_left[i-1],height[i-1]),当前柱子左边的高度和其左边柱子的左边最高高度中选择最大的，就是当前柱子左边最高的高度了。右侧同理可得。具体见代码和注释。

相当于用空间换时间了，时间复杂度降低到了O(n)，可以AC。

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        res = 0
        if n<3:
            return 0
        max_left = [0 for _ in range(n)]
        max_right = [0 for _ in range(n)]
        for i in range(1,n-1):
            max_left[i] = max(max_left[i-1],height[i-1])
        for i in range(n-2,0,-1):
            max_right[i] = max(max_right[i+1],height[i+1])
        for i in range(1,n-1):
            min_h = min(max_left[i],max_right[i])
            if min_h>height[i]:
                res += min_h-height[i]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.双指针

其实是对第二种解法空间复杂度的一个优化，用双指针取代了数组。取代之后就要注意在一次遍历的时候，判断到底是当前柱子左侧的高度更小还是右侧的高度更小，从而决定更新使用的值。具体见代码和注释。

时间复杂度为O(n)，空间复杂度为O（1）

class Solution:
    def trap(self, height: List[int]) -> int:        
        n = len(height)
        res = 0
        if n<3:
            return 0
        max_left,max_right = 0,0
        left,right = 1,n-2
        for i in range(1,n-1):
            # 从左往右更新，因为max_left是由height[left-1]推算出来的，所以当height[left-1]小于height[right+1]的时候，max_left一定小于max_right，右边的同理
            if height[left-1]<height[right+1]:
                max_left = max(max_left,height[left-1])
                if max_left>height[left]:
                    res += max_left-height[left]
                left += 1
            else:
                max_right = max(max_right,height[right+1])
                if max_right>height[right]:
                    res += max_right-height[right]
                right -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、栈

我们可以参考括号匹配，去计算每一对柱子之间的水量。
用栈去保存高度，遍历的时候如果当前高度小于栈顶高度，那么说明会由积水，我们当前高度的下标入栈。
如果当前高度大于栈顶的高度，那么说明之前的积水到这里停下了，可以计算到底有多少积水了。计算完成后，把当前的墙继续入栈，作为新的积水柱子。
总体原则：
（1）当前高度小于栈顶高度，入栈，指针后移
（2）当前高度大于栈顶高度，出栈，计算当前的柱子和栈顶之间的积水量，然后计算当前高度和新站的高度关系，重复2，直到当前柱子的高度不大于栈顶高度，或者栈为空，然后把当前柱子入栈，指针后移。

class Solution:
    def trap(self, height: List[int]) -> int:        
        n = len(height)
        res = 0
        if n<3:
            return 0
        stack = []
        for i in range(n):
            # 只要栈不为空而且当前的柱子高度大于栈顶，就可以循环比较计算
            while stack and height[i]>height[stack[-1]]:
                h = height[stack.pop()]
                if not stack:
                    break
                distance = i-stack[-1]-1
                min_h = min(height[stack[-1]],height[i])
                res += distance*(min_h-h)
            stack.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18