https://leetcode-cn.com/problems/trapping-rain-water/

0位置和最后一个位置是放不了水的

法一：预处理数组

• 把预处理数组求好，就知道每个i位置左边和右边的max了，就可以直接算然后累加了

  public int trap(int[] arr) {
    if (arr == null || arr.length < 3) {
        return 0;
    }
    int N = arr.length;
    int[] rMax = new int[N];
    rMax[N - 1] = arr[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        rMax[i] = arr[i] > rMax[i + 1] ? arr[i] : rMax[i + 1];
    }
    int lMax = arr[0];
    int water = 0;
    for (int i = 1; i < N - 1; i++) {
        water += Math.max(Math.min(lMax, rMax[i + 1]) - arr[i], 0);
        lMax = Math.max(lMax, arr[i]);
    }
    return water;
  }

  法二：双指针

  

• Lmax和rMax去pk，

  • 若Lmax小（瓶颈），则先算L位置的水量, L++（因为对于L来说，现在左边的max是真实的， 而L右边的max现在还不确定会不会有比现在的rMax大的， 但至少是现在的rMax）
  • 若rMax小（瓶颈），先算R位置的水量, R—

    public int trap(int[] arr) {
       if (arr == null || arr.length < 3) {
           return 0;
       }
       int L = 1;
       int R = arr.length - 1;
       int LMax = arr[0];
       int RMax = arr[arr.length - 1];
       int water = 0;
       while (L <= R) {
           if (LMax <= RMax) {
               water += Math.max(LMax - arr[L], 0);
               LMax = Math.max(LMax, arr[L++]);
           } else {
               water += Math.max(RMax - arr[R], 0);
               RMax = Math.max(RMax, arr[R--]);
           }
       }
       return water;
    }

• L < R 还是L <= R?

  • 想一下只有3个数的情况你就知道了