福州网站建设托管,设计师之家资源库,常州百度seo排名,公司营销网站建设给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表…给定 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.length1 n 2 * 1040 height[i] 105
// 接雨水问题解决方案类
class Solution {
public:/*** 计算给定高度图下雨后能接多少雨水* param height 一系列非负整数表示的高度图* return 返回能接的雨水总量*/int trap(vectorint height) {// 总水量int sum 0;// 高度图长度int len height.size();// 使用栈来存储高度和对应索引stackint hv;stackint 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;}
};
