【牛客题霸题解】容器盛水问题

题目可以转化为求每个位置上面能装多少水
比如题目中给出来的例子：左右两边边界(0和5位置)上是一定不会有水的，然后1位置上能装2格水，2位置上能装1格水，3位置上不能装水，4位置上能装2格水。所以对于这一个例子来说，一共能装5格水。

那么我们就再来考虑一下，每个位置上面能装多少水怎么求
对于位置 来说，它上面能装的水其实取决于
例：2位置上能装的水=
这里注意一下，像3位置这样本身高度大于 的 上面能装的水是0。要特判一下，直接带公式的话会减出负数
这样的话这道题已经可以解了。
最简单的做法就是建两个数组:

• 表示 位置左边的最大值
• 表示 位置右边的最大值

然后按照我们的步骤来求就可以了。时间复杂度 ,额外空间复杂度
但是其实还可以再优化一下空间复杂度不用开辟数组，我们定义两个指针初始, 表示 左边的最大值是多少， 表示 右边的最大值是多少
如果 的话,我们就可以知道 位置上面能装多少水了，因为虽然我们不知道 右边的最大值具体是多大，但是右边的最大值一定比 大。所以min(左右两边的最大值)一定等于。
这样的话我们就可以更新 的位置上的值，然后
同理，如果的话，也能知道 位置上面能装多少水

c++

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        int n = arr.size();
        int l = 1; 
        int r = n-2;
        long long ans = 0;
        int lmax = arr[0];
        int rmax = arr[n-1];
        while(l<=r)
        {
            if(lmax < rmax)
            {
                if( arr[l]<lmax){ans += lmax-arr[l];}
                else{ lmax = arr[l];}
                l++;
            }
            else{
                if(arr[r]<rmax){ans += rmax-arr[r];}
                else{rmax = arr[r];}
                r--;
            }
        }
        return ans;
    }
};

java

import java.util.*;
public class Solution {
    public long maxWater (int[] arr) {
        int n = arr.length;
        int l = 1;
        int r = n-2;
        long ans = 0;
        int lmax = arr[0];
        int rmax = arr[n-1];
        while(l<=r)
        {
            if(lmax < rmax)
            {
                if( arr[l]<lmax){ans += lmax-arr[l];}
                else{ lmax = arr[l];}
                l++;
            }
            else{
                if(arr[r]<rmax){ans += rmax-arr[r];}
                else{rmax = arr[r];}
                r--;
            }
        }
        return ans;
    }
}

python

class Solution:
    def maxWater(self , arr ):
        # write code here
        n = len(arr)
        l = 1
        r = n-2
        ans = 0
        lmax = arr[0]
        rmax = arr[n-1]
        while l<=r:
            if lmax < rmax:
                if arr[l]<lmax:
                    ans += lmax-arr[l]
                else:
                    lmax = arr[l]
                l=l+1
            else:
                if arr[r]<rmax:
                    ans += rmax-arr[r]
                else:
                    rmax = arr[r]
                r=r-1
        return ans