NC128 接雨水问题

二刷

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        int[] left = new int[arr.length];
        int[] right = new int[arr.length];

        long res = 0;

        for(int i=1;i<arr.length;i++){
            left[i] = Math.max(left[i-1],arr[i-1]);
        }
        for(int i=arr.length-2;i>=0;i--){
            right[i] = Math.max(right[i+1],arr[i+1]);
        }
        for(int i=0;i<arr.length;i++){
            int num = Math.min(left[i],right[i]);
            if(num>arr[i]){
                res = res + num - arr[i];
            }
        }
        return res;
    }
}

最开始 一行一行扫描，结果显示超时了
还有这个 long sum真的很坑。 之前是int 一直无法通过。
双层循环。O(N*2)。

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    private int getMax(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] > max) {
                max = height[i];
            }
        }
        return max;
    }


    public long maxWater (int[] arr) {
        int arr_max = getMax(arr);
        long sum = 0;
        for(int i = 1; i<= arr_max; i++){
            int temp = 0;
            int flag = 0; //判断是否开始计算
            for(int j=0; j<arr.length;j++){
                if(arr[j]>=i && flag == 0){
                    flag++;
                }
                if(arr[j]>=i && flag == 1){ //遇到一个比当前高的就把temp加到sum中
                    sum = sum + temp;
                    temp = 0;
                }
                if(arr[j]<i && flag == 1){
                    temp++;
                }
            }
        }
        return sum;

    }
}

2.动态规划真的很好用
动态规划代码可太简洁了， 只需要三个循环，分别算出这列 左右最高的值，然后根据木桶原理比较。

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */

    public long maxWater (int[] arr) {
        long sum=0;
        int len = arr.length;
        int[] leftmax = new int[len];
        int[] rightmax = new int[len];

        leftmax[0] = arr[0];
        for(int i=1;i<len-1;i++){
            leftmax[i] = Math.max(leftmax[i-1],arr[i-1]);
        }

        rightmax[len-1] = arr[len-1];
        for(int i=len-2; i>0;i--){
            rightmax[i] = Math.max(rightmax[i+1],arr[i+1]);
        }

        for(int i=1;i<len-1;i++){
            int min = Math.min(rightmax[i],leftmax[i]);
            if(min>arr[i]){
                sum = sum + min - arr[i];
            }
        }

        return sum;
    }
}

3.双指针还没有看