接雨水问题(官方的解法三：双指针)

要求：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路：

其实就是按列求值。关注当前列，其左边最高的墙，右边最高的墙。并关注左右两边最高墙的较矮的墙的高度。

• 较矮墙的高度高于当前列，存的水量为（较矮的墙的高度-当前列的高度）
• 较矮墙的高度等于当前列，存的水量为0
• 较矮墙的高度小于当前列，存的水量为0
• 另外，两端是肯定存不住水的

public int trap(int[] height) {
    int sum = 0;
    //两端不用考虑
    for (int i = 1; i < height.length - 2; i++) {
        int max_left = 0;
        //找到左边最高墙,从当前列从右往左遍历
        for (int j = i-1; j >= 0; j--) {
            if (height[j] > max_left) {
                max_left = height[j];
            }
        }
        int max_right = 0;
        //找出右边最高墙，从当前列从左往右遍历
        for (int j = i+1; j < height.length; j++) {
            if (height[j] > max_right) {
                max_right = height[j];
            }
        }
        //比较两端最高墙，找出较矮的墙
        int min = Math.min(max_left, max_right);
        if (min > height[i]) {
            sum += (min - height[i]);
        }
    }
    return sum;
}

动态规划进行优化

用max_left[i]代表第i列左边最高墙的高度，max_right[i]代表第i列右边最高墙的高度。实际上，max_left[i]=max(max_left[i-1], height[i-1]), max_right[i] = max(max_right[i+1], height[i+1]) 这样就不用每次都要在循环中重新求一次max_left和max_right了。但依旧存在缺点，就是需要从左向右遍历，还是需要数组来存储左右两边的最大墙。

public int trap(int[] height) {
    int sum = 0;
    int[] max_left = new int[height.length];
    int[] max_right = new int[height.length];
    
    for (int i = 1; i < height.length-1; i++) {
        max_left[i] = Math.max(max_left[i-1], height[i-1]);
    }
    for (int i = height.length-2; i >= 0; i--) {
        max_right[i] = Math.max(max_right[i+1], height[i+1]);
    }
    
    for (int i = 1; i < height.length - 1; i++) {
        int min = Math.min(max_left[i], max_right[i]);
        if (min > height[i]) {
            sum += (min-height[i]);
        }
    }
    return sum;
}

双指针的改进：

在本题中，max_left[i]和max_right[i]其实都只使用过一次，所以可以使用双指针交替前进，避免数组的使用。已知max_left = Math.max(max_left, height[i-1]),即height[left-1]是可能成为max_left的，所以只要height[left-1]<height[right+1],那么max_left就一定是小于max_right的。 此处，left代表左侧指针的索引，right代表右侧指针的索引。只要max_left<max_right,就从左往右更新，因为较矮的墙会在左侧更新，否则就从右往左更新。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;//左指针
    int right = height.length - 2;//右指针
    for (int i = 1; i < height.length - 1; i++) {
        //从左到右更新
        if (height[left-1] < height[right+1]) {
            max_left = Math.max(max_left, height[left-1]);
            int min = max_left;
            if (min > height[left]) {
                sum += (min-height[left]);
            }
            left++;
        } else {//从右往左更新
            max_right = Math.max(max_right, height[right+1]);
            int min = max_right;
            if (min > height[right]) {
                sum += (min - height[right]);
            }
            right--;
        }
    }
    return sum;
}