leetcode_【42】接雨水

1.题目描述

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

2.解题思路

思路1：转化成每个位置留下水量的总和

i位置上留下的水为[0 , (i-1)]的最大值max1,(i+1,length)位置上的max2的两者较小值-该位置的高度：min(max2-max1) - arr[i]。

思路2：依次结算每个位置的水量，max_left和max_right那边数值小结算哪边。并向中间滑动。

思路3：跟思路2一致，减掉了一个指针

思路4：左边最大值小于右边最大值，左指针右滑，左指针位置上能装的水就是左边最大值减去左指针指的值，若左指针指向的值大于左边大值，就不减，说明不能储水，更新左边最大值，当右边最大值小于左边最大值时，右指针左滑，做法跟前类似，直到左指针小于等于右指针跳出循环。

3.代码

思路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代码：

//思路2：依次结算每个位置的水量，max_left和max_right那边数值小结算哪边。并向中间滑动。
    public static int trap2(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int n = arr.length - 2;
        int[] leftMaxs = new int[n];
        leftMaxs[0] = arr[0];//左指针初始化为第一个数
        //求左边的max
        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];//右指针初始化为数组最后一个数
//求右边的max
        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代码：

//思路3：减少一个指针
 public static int trap3(int[] arr) {
     if (arr == null || arr.length < 3) {
         return 0;
     }
     int n = arr.length - 2;
     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 leftMax = arr[0];
     int value = 0;
     for (int i = 1; i <= n; i++) {
         value += Math.max(0, Math.min(leftMax, rightMaxs[i - 1]) - arr[i]);
         leftMax = Math.max(leftMax, arr[i]);
     }
     return value;
 }

思路4代码：

public static int trap4(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;
    }

4.提交记录

思路1提交记录：

思路2提交记录：

思路3提交记录：

思路4提交记录：