LeetCode Note Java 00042：Trapping Rain Water

情境題：計算最大積水量。

題目

Trapping Rain Water Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

解法

Two Pointer 從兩邊往內夾：

class Solution {
    public int trap(int[] height) {
        int output = 0, l = 0, r = height.length - 1;
        while (l < r) {
          int minBorder = Math.min(height[l], height[r]); // 以短的邊界為比較依據，因為水超過短邊就會漏掉
          if (height[l] == minBorder) {
            l++;
            while (l < r && minBorder > height[l]) { // 計算水窪
              output += minBorder - height[l++];
            }
          } else {
            r--;
            while (l < r && minBorder > height[r]) {
              output += minBorder - height[r--];
            }
          }
        }
        return output;
    }
}

檢討

關於 Two Pointer 對於移動指標的時機還不是很熟悉，常常誤判。

看了滿多其他解法，要注意不要被題目分類蒙蔽雙眼。

參考資料

[LeetCode] 42. Trapping Rain Water 收集雨水