牛客题霸 [容器盛水问题] C++题解/答案

题目描述

给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器,请返回容器能装多少水。
具体请参考样例解释

题解:

我们找出容器的左右边界,选择边界更低的,可以采用双指针,分别从两端向中间扫描,如果里面的高度高于边界就不能盛水,更新边界为当前高度,如果小于边界就可以盛水,记录答案

代码:

class Solution {
   
public:
    /** * max water * @param arr int整型vector the array * @return long长整型 */
    long long maxWater(vector<int>& arr) {
   
        // write code here
        if(arr.size()<=2)return 0;
        int l=0,r=arr.size()-1;
        int L=arr[l];
        int R=arr[r];
        long long maxx=0;
        while(l<r)
        {
   
            if(L<R)
            {
   
                l++;
                if(arr[l]>=L)
                {
   
                    L=arr[l];
                    continue;
                }
                maxx+=(L-arr[l]);
            }
            else 
            {
   
                r--;
                if(arr[r]>R)
                {
   
                    R=arr[r];
                    continue;
                }
                maxx+=(R-arr[r]);
            }
        }
        return maxx;
    }
};