这是一道 「困难」 题
题目来自：https://leetcode.cn/problems/trapping-rain-water/

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

「示例1」

func trap(height []int) int {
    n := len(height)
    if n <= 1 {
        return 0
    }
    stack := [][]int{}
    ans := 0
    for _, h := range height {
        if len(stack) == 0 {
            stack = append(stack, []int{1, h})
            continue
        }
        w := 0
        for len(stack) > 0 && h > stack[len(stack) - 1][1] {
            top := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            w += top[0]
            if len(stack) > 0 {
                
                ans += w * (min(stack[len(stack) - 1][1], h) - top[1])
                
            }
        }
        stack = append(stack, []int{w + 1, h})
    }

    return ans
}

func min(a int, b int) int {
    if a > b {
        return b
    }

    return a
}

复杂度分析

END