每天一道算法题13

【装水】给定一个数组arr, 已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水？
比如：arr={3,1,2,5,2,4},根据画出的直方图就是容器形状，该容器可以装下5格水。

解答：装水问题肯定是某个较小值为瓶颈，这里采用双指针，当左边的最大值小于右边的最大值时，左边算出水量，然后左指针移一个位置。
如果右边的最大值小于左边的最大值时，右边算出水量，然后右指针移动一个位置。直到二者相遇，第i位水量max = {Math.min(左max - 右max) - arr[i]};

public static int water(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int N = arr.length;
    int L = 1;
    int leftMax = arr[0];
    int R = N - 2;
    int rightMax = arr[N - 1];
    int water = 0;
    while (L <= R) {
        if (leftMax <= rightMax) {
            water+= Math.max(0, leftMax - arr[L]);
            leftMax = Math.max(leftMax, arr[L++]);
        } else {
            water += Math.max(0, rightMax - arr[R]);
            rightMax = Math.max(rightMax, arr[R--]);
        }
    }
    return water;

}