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;}
};