这一题，最直观的思路就是，遍历height里的每一个位置然后找出该位置左边区间的最大值与该位置右边区间的最大值，得到两个最大值后用两个最小值中的较小值减去该位置的高度，得到了在该位置上能够积累的雨水。这种直观思路的暴力实现如1所示。这个实现的时间复杂度是O（N^2），空间复杂度是O（1）。这个实现的时间复杂度过高原因是在求左右两边的最大值时重复访问了各个元素多次，因此我们能够想到用动态规划的方法将时间复杂度降低。这种思路首先将数组从左往右遍历一次求出每个位置左边的最大值以及从右往左遍历一次求出每个位置右边的最大值，再利用这两个最大值数组求出每个位置的积水量。这个实现见2，时间复杂度与空间复杂度都是O（N）。
另外一种方法，是用单调递减栈来解决的，如实现3所示，我们在遍历height时，在保证新加入的元素小于栈顶元素的前提下将元素的索引依次压入栈内。若出现某个元素大于栈顶元素所指代的元素时，说明有可能有低洼处能存水，首先我们我们弹出栈顶元素，该位置将会是低洼的水的底部，再比较该底部两端的stack[-1]和当前高度height[idx]哪个更小从而算出水的高度，再根据索引的差知道水的宽度从而算出水的面积。注意如果在弹出栈顶元素后仍然无法满足当前高度小于栈里的元素，那么说明无法形成低洼，此时退出循环。在遍历完整个height数组后我们就能求出答案。该实现的时间复杂度与空间复杂度都是O（N）但是对数组的遍历只进行了一次，而上面的动态编程实现方法1对数组遍历了两次。
最后还有一种用双指针法。我们从动态规划的方法中发现，当某个位置的左边区间的最大值大于右边区间的最大值时，积水的多少由右边区间的最大值所决定，反之亦然。因此，当左指针指的数小于右指针指的数时，我们用一个左指针从左往右遍历，并记录left_max，当左指针指的数小于left_max时，我们知道右端有一根很高的柱子并记录下这一步的积水量。当左指针指的数大于右指针指的数时，我们移动右指针，并做与前面类似的事情，直到两个指针相遇在最高的height处。返回答案。这种方法的时间复杂度为O（N），空间复杂度与之前的所有方法相比更小为O（1）。
class Solution:
def trap1(self, height: List[int]) -> int:
ans = 0
left_max, right_max = 0, 0
for i in range(len(height)):
if height[:i]:
left_max = max(height[:i])
if height[i+1:]:
right_max = max(height[i+1:])
mmin = min(left_max, right_max)
if mmin >= height[i]:
ans += mmin - height[i]
return ans
def trap2(self, height: List[int]) -> int:
left_to_right = self.find_max(height)
right_to_left = self.find_max(height[::-1])
ans = 0
min_max = [min(x, y) for x, y in zip(left_to_right, right_to_left[::-1])]
for i in range(1, len(height)-1):
tmp = min_max[i] - height[i]
ans += tmp
return ans
def find_max(self, lst):
mmax = []
max_height = 0
for i in range(len(lst)):
if max_height < lst[i]:
max_height = lst[i]
mmax.append(max_height)
return mmax
def trap3(self, height: List[int]) -> int:
length = len(height)
if length < 3:
return 0
ans, idx = 0, 0
stack = []
while idx < length:
while stack and height[idx] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
h = min(height[stack[-1]], height[idx]) - height[top]
d = idx - stack[-1] -1
ans += h * d
stack.append(idx)
idx += 1
return ans
def trap4(self, height: List[int]) -> int:
left, right = 0, len(height)-1
left_max, right_max = 0, 0
ans = 0
while left < right:
if height[left] < height[right]:
if height[left] > left_max:
left_max = height[left]
else:
ans += left_max - height[left]
left += 1
else:
if height[right] > right_max:
right_max = height[right]
else:
ans += right_max - height[right]
right -= 1
return ans