今天回顾了一道题目
给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。 解决这个问题的想法很简单，求出每个柱子上方有多少雨水，最后累加即可。而一个柱子上方有多少雨水，取决于自身的高度，以及左边柱子高度的最大值和右边柱子高度的最大值。
这样，动态规划的方法就不难理解，从左往右得到每根柱子左侧柱子高度的最大值，再从右往左得到每根柱子右侧柱子高度的最大值，最后从左往右计算每个柱子上方有多少雨水。代码如下
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0 # 没有柱子存不了雨水
n = len(height)
leftMax = [height[0]] + [0] * (n - 1)
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i]) #从左往右得到左侧柱子高度的最大值
rightMax = [0] * (n - 1) + [height[n - 1]]
for i in range(n - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i]) #从右往左得到每根柱子右侧柱子高度的最大值
ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
return ans但这种方式效率很低，其实回顾思路发现，一个柱子上方的雨水，取决于左边柱子高度的最大值和右边柱子高度的最大值。如果知道哪测比较高，那就只会用到另外一侧的最大值。所以可以改用双指针用来代替前面的数组。代码如下：
class Solution:
def trap(self, height: List[int]) -> int:
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]: # 如果无法理解这个条件，可以换成 leftMax < rightMax
ans += leftMax - height[left]
left += 1
else:
ans += rightMax - height[right]
right -= 1
return ans当时阅读leetcode官方的题解有如下的描述
如果 height[left] ≥ height[right]，则必有 leftMax ≥ rightMax
这个推论对我而言并不容易理解，但可以使用结构归纳法证明。
证明
假设有height 的数组，初始状态是left, right = 0, len(height) - 1。很显然，leftMax是height[0],rightMax是height[-1]，一定成立。
然后关键的就是递推情况。假设 现在是left == l, right == r，而height[l] ≥ height[r]，需要证明此时leftMax ≥ rightMax。
达到left == l和right == r的上一个状态有2种。
从 right == r + 1 而来
在这种情况下，不难得出leftMax ≥ min(height[r + 1],…,height[n - 1])。而height[l] ≥ height[r] ， 所以leftMax ≥ height[r]，最后leftMax ≥ rightMax。
从 left == l - 1 而来
此时根据推论，min(height[0],…,height[l - 1]) ≤ rightMax，而height[l] ≥ height[r]。
这个状态下其实 height[r] == rightMax。我们可以用反证法证明。
如果height[r] != rightMax,那么rightMax ＞ height[r], min(height[0],...,height[l - 1]) ≤ rightMax == min(height[r + 1],...,height[n - 1]). 此时right 应该大于 r，在右侧柱子高度最大值所在的索引（否则，之前right在r的时候应该继续往左移动），矛盾。
证明height[r] == rightMax以后，由于height[l] ≥ height[r]，height[l] == leftMax ≥ height[r] == rightMax。证毕。