leetcode 42 接雨水
堆栈解往往是 一个一个压入 连续地弹出
如果当前元素小于等于栈顶的元素 将其压入堆栈 因为当前元素可以被栈内的前一个元素兜住
如果当前元素大于了栈顶的元素 那么栈顶的元素可以被左边和右边的元素兜住 我们就可以计算兜住的雨水
连续弹出的时候 看以看出 雨水是被一层一层计算出来的
class Solution:
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
stack = []
res = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]: # 当前元素比栈内最后一个元素大
mid = stack.pop()
if not stack:
break
distance = i - stack[-1] - 1
bounded_height = min(height[i], height[stack[-1]]) - height[mid]
res += distance * bounded_height
stack.append(i)
return res
image.png
各种括号问题 先占坑吧...
