Leetcode之Trapping Rain Water
Leetcode之Trapping Rain Water
forrestlin
发布于 2018-05-24 11:20:47
发布于 2018-05-24 11:20:47
题目原意：给定一个整数数组，每个数代表一个柱子的高度，然后求下雨后这些柱子能储多少水，例如数组[0,1,0,2,1,0,1,3,2,1,2,1]对应的示意图如下：
解题思路：四次遍历，第一次遍历获取height最大值top，然后构造一个数组incre_height，长度和height一样，除了第一个和最后一个数和height一样，其他均是top，第二次遍历incre_height，判断当前柱子是否需要削减高度，如果当前柱子的高度比自己左右柱子都高则减少高度，减为跟自己左右柱子一样高或等于height[i]，第三次还是遍历incre_height，不过是从后面遍历到前面，判断的过程还是和上一步一样，这是为了防止由于右边柱子比自己矮而减少高度的情况，如果没有这一步，上图的倒数第3,4个柱子的高度会比正确值大1。最后一次遍历就是得到最终答案了，根据incre_height[i]-height[i]。
解题代码如下：
int trap(vector<int>& height) {
if(height.size()<3)
return 0;
int top=height[0];
for(int i=1;i<height.size();i++){
if(top<height[i])
top=height[i];
}
vector<int>increHeight;
increHeight.push_back(height[0]);
for(int i=1;i<height.size()-1;i++){
increHeight.push_back(top);
}
increHeight.push_back(height[height.size()-1]);
for(int i=1;i<height.size()-1;i++){
if(increHeight[i]>increHeight[i-1]||increHeight[i]>increHeight[i+1]){
int less=increHeight[i-1];
if(less>increHeight[i+1])
less=increHeight[i+1];
if(less<height[i])
increHeight[i]=height[i];
else
increHeight[i]=less;
}
}
for(int i=height.size()-2;i>0;i--){
if(increHeight[i]>increHeight[i-1]||increHeight[i]>increHeight[i+1]){
int less=increHeight[i-1];
if(less>increHeight[i+1])
less=increHeight[i+1];
if(less<height[i])
increHeight[i]=height[i];
else
increHeight[i]=less;
}
}
int result=0;
for(int i=0;i<height.size();i++){
result+=increHeight[i]-height[i];
}
return result;
}时间复杂度是O(n)，空间复杂度也是O(n)，应该还可以，希望对大家有所帮助。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年11月23日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读