题目

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

输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6
解释： 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

解答

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;

        stack<int> stk;
        int result = 0;

        for(int i = 0; i < height.size(); i++)
        {
            if(stk.empty())
            {
                stk.push(i);
            }
            else if(height[i] < height[stk.top()])
            {
                stk.push(i);
            }
            else if(height[i] == height[stk.top()])
            {
                stk.push(i);
            }
            else
            {
                while(!stk.empty() && height[i] > height[stk.top()])
                {
                    int bottom = stk.top();
                    stk.pop();
                    if(!stk.empty())
                    {
                        int h = min(height[stk.top()], height[i]) - height[bottom];
                        int w = i - stk.top() - 1; 
                        result += h*w;
                    }
                }
                stk.push(i);
            }
        }

        return result;
    }
};