积水问题可以用栈来解决,具体步骤如下:

  1. 从左往右遍历所有的高度,将每个高度的下标压入栈中,直到遇到一个高度比栈顶高度低的位置。

  2. 弹出栈顶元素,计算出积水的面积。如果栈顶元素弹出后栈为空,则结束计算。

  3. 重复第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 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录