題目網址：https://leetcode.cn/problems/trapping-rain-water/

題意：給 n 個非負整數, 代表每個寬度為 1 的柱子之高度圖, 計算按此排列的柱子, 在下雨後能接多少雨水。

Solution 1：（TLE 無法通過）

想法：利用暴力法, 我們計算每個 col 所能接住的水量, 因此對於每個 i 我們要在 height[0 ~ i] 和 height[i ~ (n - 1)] 中分別找出最大值 leftMax 和 rightMax, 則該 col 所能接住的水量 = min(leftMax, rightMax) - height[i]

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0, n = height.size();
        for (int i = 0; i < n; ++i) {
            auto it = height.begin();
            int leftMax = *max_element(it, it + i + 1);
            int rightMax = *max_element(it + i, it + n);
            res += min(leftMax, rightMax) - height[i];
        }
        return res;
    }
};
  • time：$O(n^2)$ ➔ 每計算一次需找出 leftMax 和 rightMax, 此過程需 $O(n)$, 總共要計算 n 次
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：利用 DP, 概念同 Solution 1, 只是我們用兩個 array leftMax 和 rightMax 來記錄, 其中 leftMax[i] 和 rightMax[i] 分別代表 height[0 ~ i] 和 height[(n - 1) ~ i] 之最大值

  • 由左往右遍歷 height 得到每一個 leftMax[i]
  • 由右往左遍歷 height 得到每一個 rightMax[i]
  • 最後計算每個 col 所能接住的雨水
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0, n = height.size();
        vector<int> leftMax(n, height.front());
        vector<int> rightMax(n, height.back());

        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(height[i], leftMax[i - 1]);
            rightMax[n - 1 - i] = max(height[n - 1 - i], rightMax[n - i]);
        }

        for (int i = 0; i < n; ++i) {
            res += min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ leftMax, rightMax

Solution 3：

想法：利用 Two Pointers, 改進 Solution 2, 因為 leftMax[i] 和 rightMax[i] 只會用到一次, 然後就再也不會用到了, 因此我們用一個變數記住即可。我們定義以下變數：

  • leftMax：左邊的最大值, 它是由左往右遍歷得到的
  • rightMax：右邊的最大值, 它是由右往左遍歷得到的
  • left：由左往右處理的當前 idx
  • right：由右往左處理的當前 idx

我們有以下定理可使用：

  • 定理一：在 idx = i 時能接住的水量是取決於左右兩邊的最大值中較小的那一個

  • 定理二：

    • 當我們由左往右處理到 left 時, 左邊的最大值 leftMax 對它而言是可信的, 但 rightMax 對它而言是不可信的
    • 當我們由右往左處理到 right 時, 右邊的最大值 rightMax 對它而言是可信的, 但 leftMax 對它而言是不可信的

由上述定理, 我們可以得到：

  • 對於 left 而言, 它左邊最大值一定是 leftMax, 就算 右邊實際最大值 ≥ rightMax, 只要 leftMax < rightMax 成立, 就能知道 left 能接住多少水(定理一), 無論右邊將來是否會出現更大的 rightMax, 都不會影響到這個結果。反之, right 也是同樣道理。

while loop 的條件為何是 left <= right, 而非 left < right ?

因為是先計算當前 ptr, 再移動 ptr 的

e.g. height = [1, 0, 3]

  • 一開始 leftMax(0) < rightMax(0) 不成立, 故處理 right ➔ 得 rightMax = 3, res = 0, right = 1
  • leftMax(0) < rightMax(3) 成立, 故處理 left ➔ 得 leftMax = 1, res = 0, left = 1
  • 此時, left = 1 = right, 若 while loop 條件為 left < right, 則無法計算到 idx = 1 位置的水量
  • leftMax(1) < rightMax(3)成立, 故處理 left ➔ 得 leftMax = 1, res = 1, left = 2
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int leftMax = 0, rightMax = 0;
        int left = 0, right = height.size() - 1;

        while (left <= right) {
            if (leftMax < rightMax) {
                leftMax = max(leftMax, height[left]); // 得到左邊最大值(含自身)
                res += leftMax - height[left];
                ++left;
            } else {
                rightMax = max(rightMax, height[right]); // 得到右邊最大值(含自身)
                res += rightMax - height[right];
                --right;
            }
        }
        return res;
    }
};
  • time：$O(n)$ ➔ while loop 遍歷 height
  • space：$O(1)$ ➔ 只需常數空間