双指针

/*
从俩端向中间靠拢的政策：
1.首先取首尾的较小值：如果内部的数组值比当前的较小值小，则表明可以存雨水，反之则不能；
2.在一次遍历完成后，需要对当前的首尾进行更新： 从较小值的一侧往中间靠扰，当出现的第一个大于该值的索引保存记录跟新。
*/

class Solution {
public:
/*
* max water
* @param arr int整型vector the array
* @return long长整型
*/
//int id(vector<int> arr,int l)
long long maxWater(vector<int>& arr) {
// write code here
/</int></int>
从俩端向中间靠拢的政策：
1.首先取首尾的较小值：如果内部的数组值比当前的较小值小，则表明可以存雨水，反之则不能；
2.在一次遍历完成后，需要对当前的首尾进行更新： 从较小值的一侧往中间靠扰，当出现的第一个大于该值的索引保存记录跟新。
*/
int l=0,r=arr.size()-1; long long sum=0;
while(l<r)
{
int n=min(arr[l],arr[r]);
for(int i=l+1;i<r;i++)
{
if(n>arr[i])
{
sum+=n-arr[i];
arr[i]=n;
}
}
//查找下一个比当前最小值大的索引值
if(n==arr[l])
{
for(int i=l+1;i<r;i++)
{
if(arr[i]>n)
{
l=i;
break;
}
}
if(arr[l]==n) return sum;
}
else
{
for(int i=r-1;r>l;i--)
{
if(arr[i]>n)
{
r=i;
break;
}
}
//表示数组内部没有比n更大的数，即表示当前无法在接雨水 直接退出
if(arr[r]==n) return sum;
}
}
return sum;
}
};