leetcode-42. 接雨水 单调栈

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

示例 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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

// 接雨水问题解决方案类
class Solution {
public:
    /**
     * 计算给定高度图下雨后能接多少雨水
     * @param height 一系列非负整数表示的高度图
     * @return 返回能接的雨水总量
     */
    int trap(vector<int>& height) {
        // 总水量
        int sum = 0;
        // 高度图长度
        int len = height.size();
        // 使用栈来存储高度和对应索引
        stack<int> hv;
        stack<int> hi;
        // 初始化栈，将第一个高度和索引入栈
        hv.push(height[0]);
        hi.push(0);
        
        // 遍历高度图
        for(int i = 1; i < len; i++)
        {
            // 当前高度小于栈顶高度，直接入栈
            if(height[i]<hv.top())
            {
                hv.push(height[i]);
                hi.push(i);
            }
            // 当前高度等于栈顶高度，更新栈顶
            else if(height[i]==hv.top())
            {
                hv.pop();
                hi.pop();
                hv.push(height[i]);
                hi.push(i);
            }
            // 当前高度大于栈顶高度，开始结算水量
            else{
                // 当栈不为空且当前高度大于栈顶高度时，循环结算水量
                while(!hv.empty()&& height[i] > hv.top())
                {
                    // 弹出栈顶，计算被夹在中间的雨水
                    int mid =hi.top();
                    hi.pop();
                    hv.pop();
                    // 如果栈不为空，说明还有边界高度可以形成容器
                    if(!hv.empty())
                    {
                        // 计算容器的高度差
                        int h = min(hv.top(), height[i]) - height[mid];
                        // 计算容器的宽度
                        int w =i -hi.top()-1;
                        // 累加水量
                        sum +=h*w;
                    }
                }
                // 当前高度入栈
                hv.push(height[i]);
                hi.push(i);
            }
        }
        // 返回总水量
        return sum;
    }
};