import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        if(arr == null || arr.length == 0){
            return 0;
        }
        int left = 0;
        int right = arr.length - 1;
        long result = 0;
        //left .. right 可以看做是一个新桶,桶的高度就是最矮的那个柱子,超过水就会漏出来咯
        //先判断桶右边低还是 左边低
        //盛水高度就是桶的高度减去我们查找的柱子的高度
        //每次从左向右 不断找到比桶高度矮的高度,找不到桶左侧就变小
        //每次也从右向左,找到比桶高度小的,找不到桶右侧就缩小
        //然后桶不断缩小
       
        while(left < right){
            //桶高
            int min = arr[left] > arr[right] ? arr[right] : arr[left];
            
            while(left < right && arr[left] <= min){
                result += min -arr[left];
                left ++;
            }
            while(left < right && arr[right] <= min ){
                result += min - arr[right];
                right -- ;
            }
        }
        return result;
    }
}