leetcode No42. Trapping Rain Water
栏目：php教程时间：2016-11-28 13:31:15
Question:
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
数组元素代表高度，如图所示，求能装多少水
Algorithm：
分别从左右两边向最高点逼近，只在元素小的1边地方储水。由左侧向最高点逼近时，设左侧当前的最大值leftmax,当前遍历到i，如果leftmax
> A[i]; sum += (leftmax- A[i]);否则，currentMax = i，此条带没法储水；由右侧逼近最高点类似左侧。
Accepted Code:
class Solution {
public:
int trap(vector<int>& height) {
int left=0;
int right=height.size()⑴;
int leftmax=0; //左侧最大值
int rightmax=0; //右侧最大值
int res=0; //结果
while(left<=right)
{
if(height[left]<=height[right])
{
if(height[left]>leftmax)
leftmax=height[left];
else
res+=leftmax-height[left];
left++;
}
else
{
if(height[right]>rightmax)
rightmax=height[right];
else
res+=rightmax-height[right];
right--;
}
}
return res;
}
};
------分隔线----------------------------
上一篇 市政智能化管理系统开发
下一篇 浅谈主流热修复技术
------分隔线----------------------------