题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
- 双指针
- 运行时间超过96%,内存量超过99%。
- 能接多少雨水,首先左右两边肯定不能接水,必须要有至少一边高于目前所在的位置才能储存雨水,那么怎么保证自己所在位置一定能接到雨水的?设置左右两边的最大值,那么问题就变成了左右两边最小的那个最大值跟当前所在位置的arr值的差值就是我们需要求的能接到的雨水量。
class Solution {
public:
long long maxWater(vector<int>& arr) {
// write code here
//定义变量
int left = 0,right = arr.size()-1;//定义左右指针
int maxleft = 0,maxright = 0;//定义左右的最大值
int ans = 0;//定义能接的雨水总量
//当左边等于右边的时候循环结束
while(left < right){
//更新左右两边的最大值,与当前指针位置的值进行比较选较大值
maxleft = max(maxleft,arr[left]);
maxright = max(maxright,arr[right]);
//(重点)比较左右最大值,更新较小的最大值,累加雨水量
if(maxleft < maxright){
ans += (maxleft-arr[left]);
left++;
}else{
ans += (maxright-arr[right]);
right--;
}
}
return ans;
}
};