【C++】19行寻找左右最高列+20行双指针

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        if(arr.size() <= 2) return 0;
        long long res = 0;
        int left_heigest[arr.size()], right_heigest[arr.size()]; //用于记录每列左右最高列，若没有比自己高的则值记为自己
        left_heigest[0] = arr[0]; //对于第一列左边最高列为自己
        right_heigest[arr.size() - 1] = arr[arr.size() - 1]; ////对于最后一列右边最高列为自己
        for(int i = 1; i < arr.size(); i++) { //更新左边最高列
            left_heigest[i] = max(arr[i], left_heigest[i - 1]); //最高列具有传递性，只需比较自己和前一列左边最高列
        }
        for(int i = arr.size() - 2; i >= 0; i--) { //更新右边最高列
            right_heigest[i] = max(arr[i], right_heigest[i + 1]); //最高列具有传递性，只需比较自己和后一列右边最高列
            int dif = min(left_heigest[i], right_heigest[i]) - arr[i]; //这里已经知道左右最高列了，和两个最高列中较小值进行差值计算
            if(dif > 0) res += dif; //大于0才能盛水
        }
        return res; //返回结果
    }
};

双指针：

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        if(arr.size() <= 2) return 0;
        long long res = 0;
        int left = 0, right = arr.size() - 1; //头尾左右指针
        int left_longest = 0, right_longest = 0; //记录左指针左边的最高值，右指针右边的最高值
        while(left <= right) { //或者left < right, 下面改成
            if(left_longest < right_longest) { //arr[left] < arr[right]
                arr[left] >= left_longest ? left_longest = arr[left] : res += left_longest - arr[left];
                left++;
            }
            else {
                arr[right] >= right_longest ? right_longest = arr[right] : res += right_longest - arr[right];
                right--;
            }
        }
        return res;
    }
};