leetcode No42. Trapping Rain Water
发布时间：2020-12-13 21:16:57 所属栏目：PHP教程 来源：网络整理
导读：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,2,3,1] ,return 6 . The above elevation map is represent
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,
The above elevation map is represented by array [0,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;
}
}; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
