在线免费做logo印章网站,自己做的旅游网站 介绍,国家工信部备案网站,寿光市网站建设接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图#xff0c;在这种情况下#xff0c;可以接 6 个单位的雨水#xff08;蓝色部分表示雨水…接雨水 给定 n 个非负整数表示每个宽度为 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
题解 暴力的话就是m*n复杂度 可能会超时 考虑一下其他方案 要求的就是蓝色区域也就是凹进去的部分。那么如何求解凹进去的部分就是要对每一块凹进去的部分得到左右两边的边界信息通过边界得到有多少块小方块可以填满那么凹进去的形状是很多样的如何正确求解我们可以对每一个高度维护一个“凹”信息也就是把凹的前半部分放到一个数据结构里那么当我们走到凹的后半部分时候就可以结合前半部分的数据进行计算也就是对每一个位置的高度如果前面有坑也就是可以积水那么我们就要拿到前面的积水左边界的高度和位置信息由此可知我们要用一个栈去维护当我遇到一个高一点的位置就要拿出之前放进去最近的左边界的信息用来计算。
栈里要用的就像是括号匹配一样的只需要记录左括号也就是凹的左边界信息那么维护一个下降高度的单调栈栈内的元素表示由近到远的递增位置信息。于是我们遍历每一个位置对当前位置 如果比栈顶元素小那么入栈进来形成一个递减的高度也就是凹左边界信息 如何和栈顶元素相同那么也就形成一个平台我们只需要保留最近的一个位置就好了用新位置代替原栈顶元素 如果比栈顶元素大表示可能形成一个凹区域就要仔细判断了我们要把所有可能和当前位置形成积水的所有之前的位置都处理掉才能计算出正确答案那就一直弹出栈顶元素直到栈空或者遇到一个比当前元素更大的位置。那么也就是栈中的元素就是维护一个每一个小凹区域的积水的信息对每一个栈顶元素我们要计算这之间的积水信息。也就需要这两个位置之间的高度差还有与地面形成的高度差才能正确计算前者好算后者就通过我们每次记录一个pre通过这个pre来计算凹区域中最凹中间的高度由此就可以计算出正确答案。
class Solution {
public:int trap(vectorint height) {stackints;int ans0,pre;for(int i0;iheight.size();i){if(s.size()) {if(height[i]height[s.top()])s.push(i);else if(height[i]height[s.top()]){s.pop();s.push(i);}else {//大于栈顶 把大于栈内的所有元素出栈pre-1;while(s.size()height[i]height[s.top()]){if(pre-1)pre height[s.top()],s.pop();else {ans(i-s.top()-1)*(min(height[i],height[s.top()])-pre);preheight[s.top()];s.pop();}}if(s.size()height[i]height[s.top()]){ans(i-s.top()-1)*(min(height[i],height[s.top()])-pre);if(height[i]height[s.top()])s.pop(),s.push(i);}s.push(i); }}else {if(height[i]0)s.push(i);else continue;}}return ans;}
};
相关文章：
