面试题17.21.直方图的水量.md

面试题 17.21. 直方图的水量

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解法

单调递减栈，栈内存储数组的下标；

遍历数组，栈顶元素比当前元素更矮就出栈，并计算蓄水量。

func trap(height []int) int {
	if len(height) == 0 {
		return 0
	}
	var res int
	var stack []int // 单调递减栈， 里面存的是idx
	for i, h := range height {
		for size := len(stack); size > 0; {
			lastH := height[stack[size-1]]
			// 递减，则直接入栈
			if h < lastH {
				break
			}
			// 递增，则出栈元素
			stack = stack[:size-1]
			size = len(stack)
			// 如果栈形如 [3，1]，出栈1后里面还有元素，才可以计算蓄水量，否则没必要计算
			if size > 0 {
				res += (min(h, height[stack[size-1]]) - lastH) * (i - stack[size-1] - 1)
			}
		}
		stack = append(stack, i)
	}
	return res
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}