题目：接雨水

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

image
image

  • 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

来源：力扣（LeetCode）第42题

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

分析：

方法太多了，一道极难题，从暴力法，到动态规划，再到单调栈，再到双指针。方法非常多，也很难理解，暴力法最好理解，dp和双指针稍难，我这里讲单调栈的方法。

思路：

  • 维护一个单调递减栈。
  • 当有值比栈顶元素大的时候做这么几件事情：
    • 先出栈一个元素并保存到top中。
    • 然后判断stack是否是空，如果是空的话，说明出栈的左边没有东西，所以无法装雨水。(一定要两边都要有东西并且两边的墙比出栈的墙要长，这样才能装雨水)
    • 算出当前元素与栈顶元素中间的距离dis(注意现在是出栈之后的栈顶元素)
    • 算出当前元素与栈顶元素中哪个值最小，并将小的那个值与出栈的那个元素相减，得到floor_cnt
    • 为什么要叫floor_cnt呢，因为将floor_cnt与dis(也就是两栋大墙之间的距离)相乘，你就能得到在这两栋墙之间一层的雨水数量。
    • 将它们加到ans答案中。例如：如果两栋墙最小的那栋是3，那么就会有3层，每一层的雨水数量可能是不一样的，所以要算3遍。
    • 最后返回ans得到答案。
  • 如果值比栈顶元素小的话就入栈就行了，这样就能维护单调递减栈。(注意栈中存的是数组下标，为了算起来方便。)

Talk is cheap,show me the code.

class Solution(object):
    def trap(self, height):
        stack = []
        ans = 0
        cur = 0
        while cur < len(height):
            while stack and height[stack[-1]] < height[cur]:
                top = stack.pop()
                if not stack:
                    break
                dis = cur - stack[-1] - 1
                floor_cnt = min(height[stack[-1]], height[cur]) - height[top]
                ans += dis * floor_cnt
            stack.append(cur)
            cur += 1
        return ans

顺便写上双指针法：

class Solution:
    def trap(self, height: List[int]) -> int:
        lMax = 0
        rMax = 0
        res = 0
        i = 0
        j = len(height) - 1
        while i < j:
            if height[i] < height[j]:
                if height[i] >= lMax:
                    lMax = height[i]
                else:
                    res += (lMax - height[i])
                i += 1
            else:
                if height[j] >= rMax:
                    rMax = height[j]
                else:
                    res += (rMax - height[j])
                j -= 1
        return res

复杂度分析：

  • 时间复杂度：O(n) n 为height长度
  • 空间复杂度：O(n) n为stack长度。最坏情况下完全是单调递减栈，n变为height的长度。

总结：

  • 这是一道hard题。难度挺大的，其实我自己第一次想的时侯方法已经很接近了，但就是那个突破口没有想到，导致做不出来。
  • 如果我能想到一层一层算的话这道题就能解决了。
  • 而且这道题非常经典，有非常多的解法，建议大家收藏。