【力扣】第42题：接雨水

原文链接：42. 接雨水 - 力扣（LeetCode）

1、题目解析

解读：给定一个数组，使数组的值为高形成柱子，按照短板效应原理能剩多少水。

核心思想：

        每一个坐标位置可以承装的水= min(左边最高柱子，右边最高柱子）- 该坐标值

2、编码实现

方法一

我们可以用两个数组，一个用来记录每一个坐标值的左边中柱子的最高值，一个用来记录每一个坐标值右边中柱子的最高值。当我们要记录某一个坐标值能盛装多少水时，根据上面提供的公式，只要在这两个数组中取出该坐标对应的值即可。

    /*
    * 方法一：时间复杂度O(n)，空间复杂度O(n)
    * 思路：对于每个位置i，能装的水量是：min(左边最高的柱子，右边最高的柱子)-height[i]
    *  1.先计算每个位置左边最高的柱子，存入pre_Max数组
    *  2.再计算每个位置右边最高的柱子，存入suf_Max数组
    *  3.遍历每个位置i，计算能装的水量，并累加到ans中
    * */
    public static int trap(int[] height) {
        int ans = 0;

        int len = height.length;
        int[] pre_Max = new int[len];
        pre_Max[0] = height[0];
        for(int i = 1;i<len;i++){
            pre_Max[i] = Math.max(pre_Max[i-1],height[i]);
        }
        int[] suf_Max = new int[len];
        suf_Max[len-1] = height[len-1];
        for(int j = len-2;j>=0;j--){
            suf_Max[j] = Math.max(suf_Max[j+1],height[j]);
        }
        int a=1;
        for(int k = 0;k<len;k++){
            int min = Math.min(suf_Max[k],pre_Max[k]);
            ans += min-height[k];
        }
        return ans;
    }

方法二：双指针

1. 两指针分别从数组左右端点开始遍历
2. 两个指针记录的是遍历到的最高值
3. 对比左右指针的当前值，谁小谁移动
4. 当指针遍历到某一节点时，因为是谁小谁移动，所以另一个指针的值一定是比当前指针的值大的，也就是说另一侧更高。
5. 所以让盛装的水量+（当前这一侧的最大值 - 当前指针的值）

编码实现：

/*
     * 优化：可以使用双指针，时间复杂度O(n)，空间复杂度O(1)
     *  方法二：双指针
     * 
     *  思路：使用双指针，左指针left和右指针right，初始时分别指向数组的两端
     *  1、两指针分别从数组左右端点开始遍历
     *  2、两个指针记录的是遍历到的最高值
     *  3、对比左右指针的当前值，谁小谁移动
     *  4、当指针遍历到某一节点时，因为是谁小谁移动，所以另一个指针的值一定是比当前指针的值大的，也就是说另一侧更高。
     *  5、因此可以计算当前指针能装的水量：ans += pre_max - height[left] 或 ans += suf_max - height[right]
     * 
     *  时间复杂度O(n)，空间复杂度O(1)
     *  注意：如果数组长度小于3，则无法形成容器，直接返回0
    * */
    public static int trap2(int[] height) {
        int ans = 0;
        int len = height.length;
        int left = 0,pre_max = 0;
        int right = len-1,suf_max = 0;

        while(left<=right){
            pre_max = Math.max(pre_max,height[left]);
            suf_max = Math.max(suf_max,height[right]);
            if(pre_max<suf_max){
                ans += pre_max-height[left];
                left++;
            }else {
                ans += suf_max-height[right];
                right--;
            }
        }
        return ans;

    }