我的原文链接：http://ben-personal.top/2020/04/leetcode-42-traprain/
这道题将对比三种方法，分别是动态规划、双指针（改进的动态规划）和单调栈法。通过这道题至少可以感受到两方面的进步：
- 看问题的视角不同，形成的算法也完全不同
- 动态规划常常可以进行空间上的改进
题目如下：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图如下，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例
解法一 动态规划
这一方法的基本思想在于，任一位置的存雨量取决于其左右最高柱子的较小者，这也是所谓木桶效应，最终值应为：
min{左边最高柱子高度，右边最高柱子高度} - 该位置柱子高度
那这和动态规划有何关系呢？关键就在于左右最高柱子的高度获取上。如果迭代到每个位置都重新计算一遍左右最高柱子，显然是不合算的。如果能发现相邻位置之间的如下关系：
# 记H(i)为柱子i左边最高的柱子高度，则
H(i+1)=max{柱子i的高度，H(i)}
那就意味着不必每次重新计算，如果存储下这些数据，则可节省大量的时间。
由此诞生动态规划法，用两个数组存下每个位置左右的最大高度即可：
def trap(self, height: List[int]) -> int:
num_cols = len(height)
if num_cols < 3:
return 0
ans = 0
h_left = [0]
h_right = [0] #反过来的
for i in range(num_cols-1):
h_left.append(max(height[i], h_left[-1]))
h_right.append(max(height[num_cols-1-i], h_right[-1]))
for i in range(num_cols):
ans += max(0, min(h_left[i], h_right[num_cols-1-i]) - height[i])
return ans
解法二 双指针法
前面说过，这种方法又称为改进的动态规划法，是因为它就是在解法一的基础上衍生出来的。由于解法一中，数组中存储的每个数值只用过一次就不再使用，那能不能在用的时候算一次就好呢？
用两个指针从左右同时出发，这样可以分别获得左侧和右侧的最高柱子高度。由于存雨量取决左右最高柱子高度的较小者，因此，对于左指针所指的位置来说，一旦其左侧最大值比右侧的已知的最高高度小，则可以判定其左侧最大值比右侧的真实的最高高度（目前未知）小。这时左指针所指位置的雨量可以计算（如图蓝色部分），右侧同理。
ill.png
def trap(self, height: List[int]) -> int:
ans = 0
left = 0 # 左指针的index
h_left = 0 # 左侧最高的高度
right = len(height) - 1 # 右指针的index
h_right = 0 # 右侧最高的高度
while left <= right:
if h_left > h_right: # 意味着h_left也 >right，也 >h_right
h_right = max(height[right], h_right)
ans += h_right - height[right]
right -= 1
else:
h_left = max(height[left], h_left)
ans += h_left - height[left]
left += 1
return ans
解法三 单调栈法
这种方法相对难以理解一些，不过提供了另一个看问题的角度。前两种方法是逐列统计雨量的，而单调栈法则是分块逐层统计雨量。
所谓单调栈，是指栈中元素是绝对有序的。当即将入栈的值不符合栈中的顺序时，则需要将栈顶元素出栈，直到能够满足顺序时才能入栈。
就本题而言，考虑一个单调递减的栈，即栈顶元素最小。因为当后入栈的柱子高度较小时，是不可能存下雨水的（见下图）。只有当即将入栈的柱子高度比栈顶的大时，才开始存下雨水。
ill.png
那具体存下了多少呢？从栈顶即将出栈的柱子来看（图中右侧第二个），雨量加上本身的高度不能超过左右柱子中较低者，故雨量为深蓝部分。
当此柱子出栈后，继续比较栈顶元素与即将入栈的柱子高度，发现仍然小，那仍然可以存下雨水，其雨量为（左右柱子中较低者-本身的高度）*2，即浅蓝部分。为什么乘2？从图中容易看出，上一个出栈的元素并没有考虑到这一部分雨量。
直到栈顶柱子比即将入栈的柱子高或栈为空时，将此柱子入栈。总的来说，从图像可以看出，这是分层计算雨量，与之前的解法角度明显不同。实现代码如下：
def trap(self, height: List[int]) -> int:
if not height:
return 0
stack = [] # 存储高度的index
ans = 0 # 结果雨水量
for i in range(len(height)):
if stack:
if height[i] <= height[stack[-1]]:
stack.append(i)
else:
while height[i] > height[stack[-1]]:
stackTop = stack.pop()
while stack and height[stack[-1]] == height[stackTop]:
stackTop = stack.pop()
if stack:
ans += (i-stack[-1]-1) * (min(height[i], height[stack[-1]])-height[stackTop])
else:
break
stack.append(i)
else:
if height[i] != 0:
stack.append(i)
return ans
通过对动态规划的改进，我们发现，当动态规划的数组中元素利用率低时，常常可以改进算法，节省空间。同时，通过本问题，也可以了解单调栈的应用，类似的数据结构还有单调队列，可以自行学习。
网友评论