package
0.0.0-20230809123828-b071cee2968a
Repository: https://github.com/codehanhan/leetcode-go.git
Documentation: pkg.go.dev
# README
面试题 17.21.直方图的水量
1. 题目描述
给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 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
标签
栈
数组
双指针
动态规划
单调栈
2. 解题
对于下标 i,水能到达的最大高度等于下标 i 两边的最大高度的最小值,下标 i 处能接的水的量等于下标 i 处的水能到达的最大高度减去 height[i]。
可先倒序遍历,记录每个位置右边的最大值。再顺序遍历,记录每个位置左边的最大值。最后求出所盛水量。