双指针思想的运用

题目：

image.png

题目解析：

image.png

根据题目可以画出上图，上图中阴影部分即可以装水的部分，传统的思路是找凹槽，但是这种思路有瓶颈比如你找一定部分区域的凹槽，但是在本区域外部，也就是本区域的两侧的最高立方体都比凹槽高，即把凹槽页包含进去了，这样计算成本高，实现复杂，如下图这种情况

image.png

所以在这里我们就想到了，只看i位置的上方能够装几个格子的水，怎么看呢，如下图

image.png
在这个图上，5位置上能够装水的格数是5，图上的10是5左侧所有值的最大值，15是5右侧所有值的最大值，5位置上之所以最多能够装5格水的想法类似于，木桶问题，决定木桶装水的不是最高点，而是最低点。这就是解决此题的整体思路

方法1（不好）:

暴力循环，找i位置左侧和右侧的最大值，然后计算i位置的装水的格数

代码1：

public static int getWater1(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int value = 0;
        for (int i = 1; i < arr.length - 1; i++) {
            int leftMax = 0;
            int rightMax = 0;
            for (int l = 0; l < i; l++) {
                leftMax = Math.max(arr[l], leftMax);
            }
            for (int r = i + 1; r < arr.length; r++) {
                rightMax = Math.max(arr[r], rightMax);
            }
            value += Math.max(0, Math.min(leftMax, rightMax) - arr[i]);
        }
        return value;
    }

方法2（辅助数组）：

创建两个辅助数组，left_Max[]和right_Max[]，两个数组分别装的是从左到i位置累计的到i位置的最大值和从右到i，如下图

image.png

有了辅助数组之后，i位置的最大值和最小值就不用暴力循环找，直接从数组里取即可。
注意辅助数组的大小，是从arr原数组的第一个位置而不是第零个位置开始到数组的倒数的第二个位置，即长度是arr.length-2

代码2：

public static int getWater2(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int n = arr.length - 2;
        int[] leftMaxs = new int[n];
        leftMaxs[0] = arr[0];
        for (int i = 1; i < n; i++) {
            leftMaxs[i] = Math.max(leftMaxs[i - 1], arr[i]);
        }
        int[] rightMaxs = new int[n];
        rightMaxs[n - 1] = arr[n + 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMaxs[i] = Math.max(rightMaxs[i + 1], arr[i + 2]);
        }
        int value = 0;
        for (int i = 1; i <= n; i++) {
            value += Math.max(0, Math.min(leftMaxs[i - 1], rightMaxs[i - 1]) - arr[i]);
        }
        return value;
    }

方法3（双指针）：

分别有两个指针，指向数组的开始和最后一个位置，初始化从左边开始的最大值和从右边开始的最大值，比较左边最大值和右边最大值的大小，小的那一边的value加上然后移动，大的那一边不动，因为比如下图的形式

image.png

最开始6小于10，所以leftMax右移，因为在6的右侧的最大值>=10，所以依据最小边才能装进水的原则选左边

代码3：

    public static int getWater4(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int value = 0;
        int leftMax = arr[0];
        int rightMax = arr[arr.length - 1];
        int l = 1;
        int r = arr.length - 2;
        while (l <= r) {
            if (leftMax <= rightMax) {
                value += Math.max(0, leftMax - arr[l]);
                leftMax = Math.max(leftMax, arr[l++]);
            } else {
                value += Math.max(0, rightMax - arr[r]);
                rightMax = Math.max(rightMax, arr[r--]);
            }
        }
        return value;
    }