Leetcode每日一题 面试题 17.21. 直方图的水量

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

---

看到这题想到了单调栈，维护一个递减的单调栈存储下标，一旦遇到比栈顶对应的元素大的元素，证明可以存水。

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

    }
};

cnt 每次加上当前行的储水量，也就是说，一旦遇到比栈顶元素大的情况，我们记录当前栈顶元素位置为minn，然后弹出，然后知道左边墙的高度为height[s.top()]，求左边墙与右边墙之中的最小值，减去minn就是高度，然后i是当前位置，s.top()是左边墙的位置，右墙减去左墙再减一等它们之间的宽度，这样我们就得知了两个墙之间的行水量一共有多少。

就拿这幅图举例子，蓝色是我们第一次计算的面积，红色是第二次。