Leetcode-Trapping Rain Water 接雨水

1 题目描述

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

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

示例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

2 思路及解法

2.1 单调栈

2.1.1 思路

复杂度

时间复杂度是 $O(n)$

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

这道题官网将其属于栈解决的范畴，我们先尝试使用其来解决。

首先我们可以直接从题意中得知只有两边高中间低的时候才能装得下水，对此我们就可以使用一个单调递减栈。将递减的元素存进去（注意我们栈中存放的是元素的索引），一旦发现当前的元素大于栈顶元素了，那么就有可能会装的下水，此时我们当前的数字是右边界，栈顶的元素就是坑槽的最低点，栈从顶向下第二个元素就是左边届，然后取左右边界较小的值为装水的绝对水位，然后此高度减去水槽最低点的高度，再乘以左右边界间的距离就是装水量了，然后循环依次往后。

2.1.2 代码

伪代码

for 遍历水位数据:
    while 栈非空并且当前元素大于栈顶元素:
        取出栈顶索引
        获取边界计算当前面积
    当前索引入栈
返回面积

源码：

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = list()
        res = 0

        for i in range(len(height)):
            while stack and height[stack[-1]] < height[i]:
                curr = stack.pop()
                if not stack: break
                res += (min(height[stack[-1]], height[i]) - height[curr]) * (i - stack[-1] - 1)
            stack.append(i)

        return res

2.2 双指针

2.2.1 思路

复杂度

时间复杂度是 $O(n)$

空间复杂度：$O(1)$

第二种使用双指针来解决，可以只遍历一次，因为当前列是由左右两侧最高值的min值决定的。

当我们发现另外一侧不是最高的，则开始从相反方向开始遍历，比如右侧相比较左侧矮一点，那么就从右向左移。

2.2.2 代码

伪代码

while 左指针 < 右指针：
    if 左指针所指值 < 右指针所指值:
        if 左边最大值 大于 当前左指针所指值:
            面积叠加
        else
             更新 左边最大值 
        左指针++
    else:
        if 右边最大值 大于 当前右指针所指值:    
            面积叠加
        else
             更新 右边最大值
        右指针--
返回面积

源码：

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        res = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    res += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    res += right_max - height[right]
                right -= 1

        return res