题解 | JAVA 双指针 #接雨水问题# [P0]

双指针l, r从两边向中间逼近

lMaxH记录l左侧最高的柱子高度
rMaxH记录r右侧最高的柱子高度

核心思想是:
 - 如果lH < rH
   那么所有l左侧的柱子也 < rH (i.e. lMax < rH).
   如果同时lH < lMaxH, 则l的盛水量为lMaxH-lH 
     i.e.l被lMax和r两高柱相夹, lMax为短板.
     
时间 O(n), 空间 O(1)

import java.util.*;

public class Solution {
    public long maxWater (int[] arr) {
      if (arr.length <= 2) return 0l;
      
      int l = 0, r = arr.length-1;
      int lMaxH = 0, rMaxH = 0;
      long water = 0;
      while (l < r) {
        int lH = arr[l], rH = arr[r];
        if (lH <= rH) {
          water += Math.max(0, lMaxH - lH);
          lMaxH = Math.max(lH, lMaxH);
          l++;
        } else {
          water += Math.max(0, rMaxH - rH);
          rMaxH = Math.max(rH, rMaxH);
          r--;
        }
      }
      return water;
    }
}

之前写的奇奇怪怪的双指针算面积。留着自己复习看。

preMaxIdx指向之前最高，i指向当前柱子
如果i比preMaxIdx高, 加水。
加水量 = (i与preMaxIdx相夹的空间) - (i与preMaxIdx相夹的柱子总高)
从左向右走一遍(preMaxIdx在左侧)，从右向左再走一遍(preMaxIdx在右侧)
i与preMaxIdx等高只在从左向右时计算(避免double-counting)。
时间 O(n), 空间 O(1)

import java.util.*;

public class Solution {
  static long blocks = 0;  // 当前柱子和前高之间的方块数量
  static long water = 0;   // 已存水的总量
  static int preMaxIdx = 0;  // 前高的下标
  
  public long maxWater (int[] arr) {
    if (arr.length <= 2) return 0;
    // 从左向右找更高
    for (int i = 1; i < arr.length; i++) update(i, arr);
    // 从右向左找更高
    preMaxIdx = arr.length-1; blocks = 0;
    for (int i = arr.length-2; i >= 0; i--) update(i, arr);

    return water;
  }
  
  void update(int curIdx, int[] arr) {
    long curH = arr[curIdx];
    long preMaxH = arr[preMaxIdx];
    
    if (curH > preMaxH || 
        // 两柱等高只计算一遍 (i.e. 从左向右时计算)
        (curH == preMaxH && preMaxIdx < curIdx)) {
      // 如果当前柱子高于之前最高，盛水量 = 两柱相夹的空间 - blocks
      water += (Math.abs(preMaxIdx - curIdx) - 1) * preMaxH - blocks;
      preMaxIdx = curIdx;
      blocks = 0;
    } else {
      blocks += curH;
    }
  }
}