LeetCode 面试题 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

单调栈~
首先我们不妨思考一下，什么时候能存水，肯定要出现两高夹一低才行，此时我们把存的水看作是一个矩形，假设遍历到某一高度 $i$ 时，出现了两高夹一低的情况，中间下标为 $top$，左侧为 $left$，那么这个矩形的宽就是 $i-left-1$，高就是 $min(height[i],height[left])-height[top]$。综上，只要每出现一次两高夹一低时，把矩形面积加到答案里即可~
而我们需要用一个数据结构来维护高度，显然高度是要递增的，所以很容易想到单调栈，AC代码如下：

class Solution {
public:
    int trap(vector<int> &height) {
        int ans = 0;
        stack<int> s;
        int n = height.size();
        for (int i = 0; i < n; i++) {
            while (!s.empty() && height[i] > height[s.top()]) {
                int top = s.top();
                s.pop();
                if (s.empty()) break;
                int left = s.top();
                int w = i - left - 1;
                int h = min(height[left], height[i]) - height[top];
                ans += h * w;
            }
            s.push(i);
        }
        return ans;
    }
};