【数据结构与算法】Leetcode42 接雨水I - 困难（动态规划、单调栈、双指针、堆）

发表于 2021-05-29 分类于数据结构与算法阅读次数：

本文字数： 3.3k 阅读时长 ≈ 3 分钟

接雨水I算是Leetcode上比较经典而且有意思的题了，解法也有挺多的，有官方题解介绍的动态规划、单调栈、双指针，还有我补充的堆解法，这篇文章不是搬运文，而是对官方题解的补充，而且将接雨水II的解法移植到了接雨水I中，展示了更通用的这类题型的解法和思路。

来源：力扣

题目描述

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

示例 1：
输入：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：
输入：height = [4,2,0,3,2,5]
输出：9

这个问题官方题解中给出了三种解法：动态规划、单调栈和双指针，个人感觉动态规划的解法虽然一般很巧妙但是有时候不是很容易想到，官方题解中的双指针解法虽然是针对动态规划解法的优化，但是引出了一个更通用的解这类题目的思路，这个思路可以用来解决接雨水II，单调栈的解法则更为通用。所以个人推荐掌握顺序为：单调栈$\rightarrow$双指针$\rightarrow$动态规划。

动态规划

动态规划的解法官方题解说得很清楚，这里不再赘述。

单调栈

我之前写过一篇专门介绍单调栈的文章：【数据结构与算法】单调栈，这篇文章通过几个简单的例子来帮助理解单调栈，有兴趣可以去看一看。

这里我只说我的思路，有兴趣的可以自己去看官方题解的思路。

分析为什么这题可以用单调栈：
某个位置能否积水和能积多少水是由该位置左右两边柱子的情况确定的，如果该位置左边或右边没有比它高的柱子那么肯定没法积水，如果左右两边都有比它高的柱子那么肯定可以积水，积水量由左右两边较低的柱子决定。
单调（递增）栈可以方便地找出某个位置左边和右边离它最近且比它大的位置，所以和前面的分析有些相似之处，但是直接用好像又不太行，因为假如比单调栈找到的最近位置更远的位置有更高的柱子的话，其实可以积更多的水。
为了能用单调栈我们需要进一步分析和假设，假定我们用单调栈找出了位置i的左右两边最近且比它高的柱子j和k，我们先不考虑j到i和i到k中间比i低的柱子的积水，我们只算以当前位置height[i]为底，j到k所夹区域长度为宽，min(height[j], height[k])为顶所围矩形的积水量：(min(height[i], height[k] - height[i]) * (k - j - 1)，经过简单的画图分析我们就可以知道刚才没有考虑的比height[i]低的积水在我们遍历到对应柱子的时候就会被补上了，同样地，我们没有考虑的比最近位置远的更高位置的积水部分在我们遍历到更高的柱子时也会被补上。分析到这里其实已经可以直接写代码了，需要注意的是如果左边或者右边没有比当前位置低的柱子就直接忽略即可，因为对积水量没有贡献。下面的代码对应于我单调栈那篇文章中有重复元素数组的模版。

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
n = len(height)
stack, res= [], 0

for i in range(n):
    while stack and height[i] > height[stack[-1][0]]:
        # cur表示当前遍历的柱子
        cur = stack.pop()
        # 只有存在左边界时才能积雨水
        if stack:
            # 宽为左边最近且比当前值大的边界和右边最近且比当前值大的边界相夹的区域
            w = i-1 - stack[-1][-1]
            # 高度为两边界小的高度和当前高度之差
            h = min(height[i], height[stack[-1][-1]]) - height[cur[0]]
            res += w * h

    if stack and height[i] == height[stack[-1][0]]:
        stack[-1].append(i)
    else:
        stack.append([i])

# 不用考虑stack剩下的元素，因为剩下的元素都是没有右边界的，也无法积雨水
print(res)
# 6

双指针

虽然官方题解中也已经介绍了双指针，但是官方题解只介绍了“形”，却没有说到“神”即本质，知道了本质才能进一步扩展去解决更复杂的问题，比如接雨水II，遇到这类复杂的问题双指针就无能为力了。

# 官方的双指针解法
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
ans = 0
left, right = 0, len(height) - 1
leftMax = rightMax = 0

while left < right:
    leftMax = max(leftMax, height[left])
    rightMax = max(rightMax, height[right])
    if height[left] < height[right]:
        ans += leftMax - height[left]
        left += 1
    else:
        ans += rightMax - height[right]
        right -= 1

print(ans)
# 6

从官方的双指针代码可以看到，其实每次都是处理两个指针对应柱子较低的那个，相当于是动态地处理最小值，从数组两端一层一层地向数组中心靠近。

双指针整个过程可以看作是：

先从数组两端开始注水，leftMax和rightMax相当于左右两边水面的当前高度
遇到比水面低的就计算积水量，遇到比水面高的就抬高水面至与之平齐
为了不让一边水面比另一边水面高太多即保证整体的水面是逐步升高的，每次都挑height[left]和height[right]较低的那一边继续向中间靠拢即继续注水
水面已经经过的部分不会重新计算积水量，这样保证left和right两指针相遇后放完水后的积水量和计算得到的积水量一致。
优先队列（堆）

这个过程除了用双指针还可以用优先队列即堆（小顶堆）这个数据结构来处理，过程大概是：
先把数组两端的高度和位置放进堆中
然后弹出堆顶元素，堆顶元素的高度就可以看作是当前水面高度
判断当前位置的下一个相邻位置的高度和当前水面的大小关系，如果比水面低就计算积水量，如果比水面高跳过计算积水量
然后将高度（该位置的高度和当前水面高度较高的那个）和位置加入堆中，这样更新高度可以保证水面不会下降
然后重复这个过程直至堆为空。

在这题里其实堆在效果上跟双指针是一样的，但是用堆的话我们不用自己去决定移动左右哪个指针，只需要额外用一个数组visited来保证不会重复访问同一个位置，而且用堆还能用同样的思想解决更复杂的问题，比如下面的接雨水II，所以这题也提供了堆的解法。

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
n = len(height)
if n < 3:
    return 0

pq = []
# 保证每个位置只会被访问一次
visited = set([0, n-1])
# 只可能向左或者向右移动一位
dirs = (-1, 1)
ans = 0
# 初始化左右入口
heapq.heappush(pq, (height[0], 0))
heapq.heappush(pq, (height[n-1], n-1))

while pq:
    # 相当于弹出左右指针中较小的那个
    h, i = heapq.heappop(pq)
    # 其实在一维数组中只可能向一个方向走，因为不能走回头路
    for d in dirs:
        new_i = i + d
        if 0 <= new_i < n and new_i not in visited:
            # 如果相邻的新位置比当前柱子低，那么肯定能积水
            if height[new_i] < h:
                # 积水量直接等于高度差
                ans += h - height[new_i]
            # 相当于指针向中移动一位
            heapq.heappush(pq, (max(h, height[new_i]), new_i))
            # 表示已经访问过该位置
            visited.add(new_i)

print(ans)
# 6

题目描述

动态规划

单调栈

双指针

优先队列（堆）