题解 | #接雨水问题#
接雨水问题
https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
基本思路：使用双指针向中间逼近即可
1.使用双指针
2.使用两个值记录下双指针的左右值，同时如果遇到比自己大，则必须更新当前值，用于计算结果
class Solution {
public:
long long maxWater(vector<int>& arr) {
// write code here
//基本思路，就是两边开始，由低的往高处找，遇到比自己更高的就更新当前值，遇到比自己低的就
//计算当前可以成的雨水数
int size = arr.size();
int left = 0;
int right = size - 1;
long long res = 0;//记录最后的结果，也即雨水值
long long templ = arr[left];//记录左指针的值，指针会一直更新，但是templ必须要遇到更大的值才更新
long long tempr = arr[right];//记录右指针的值
//如果是遇到left刚好等于right- 1，此时不会影响最后的结果，所以这里用的是left < right - 1
while(left < right - 1)
{
//当左边维护的值小于右边维护的值
if(templ < tempr)
{
left++;//自加
//如果left指针指向的值小于之前维护的值，则说明可以接到雨水
if(arr[left] <= templ)
{
res += (templ - arr[left]);
}
//接不到雨水，则更新自己的左值
else{
templ = arr[left];
}
}
else
{
right--;
if(arr[right] <= tempr)
{
res += (tempr - arr[right]);
}
else{
tempr = arr[right];
}
}
}
return res;
}
};
