LeetCode链接
计算每一列可以接的雨水 对每一列 寻找其左右的最大高度 时间复杂度 O(N^2)class Solution:
def trap(self, height: List[int]) -> int:
sum = 0
heightLen = len(height)
for i in range(1, heightLen - 1):
curHeight = height[i]
# 初始高度设为 当前列的高度 向两边寻找更高的列
maxLeft, maxRight = curHeight, curHeight
for j in range(0, i):
maxLeft = max(maxLeft, height[j])
for j in range(i + 1, heightLen):
maxRight = max(maxRight, height[j])
sum += min(maxLeft, maxRight) - curHeight
return sum
动态规划 预先处理好 元素i 及其左右两边的最大值 时间复杂度 O(N)
class Solution:
def trap(self, height: List[int]) -> int:
heightLen = len(height)
# i 及其 左边的最大值 index 0 没有左边 最大值为本身 从左往右
leftMax = [height[0]] + [0] * (heightLen - 1)
# 同上 index len-1 没有右边 最大值为本身 从右往左
rightMax = [0] * (heightLen - 1) + [height[-1]]
for i in range(1, heightLen):
# i及其左边的最大值 = max(i - 1 及其左边的最大值, i本身的值)
leftMax[i] = max(leftMax[i - 1], height[i])
for i in range(heightLen - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
return sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(1, heightLen - 1))
单调栈 时间复杂度O(N)
class Solution:
def trap(self, height: List[int]) -> int:
indexStack = []
sum = 0
for i in range(len(height)):
while indexStack and height[i] > height[indexStack[-1]]:
bottom = indexStack.pop()
# 如果退栈之后栈为空 则没有左边界 不会有积水
if not indexStack:
break
left = indexStack[-1]
# 两墙之间的距离 * (两墙最小高度 - 弹出的底部的高度)
sum += (i - left - 1) * (min(height[i], height[left]) - height[bottom])
indexStack.append(i)
return sum



