用栈实现积水问题
积水问题可以用栈来解决,具体步骤如下:
-
从左往右遍历所有的高度,将每个高度的下标压入栈中,直到遇到一个高度比栈顶高度低的位置。
-
弹出栈顶元素,计算出积水的面积。如果栈顶元素弹出后栈为空,则结束计算。
-
重复第1、2步,直到遍历完所有的高度。
下面是Python代码实现:
def trap(height):
stack = []
water = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
left = stack[-1]
distance = i - left - 1
h = min(height[left], height[i]) - height[top]
water += distance * h
stack.append(i)
return water
其中,height是一个列表,表示每个位置的高度。
原文地址: https://www.cveoy.top/t/topic/bHph 著作权归作者所有。请勿转载和采集!