Hard
Related Topics: Array / Two Pointers / Dynamic Programming / Stack / Monotonic Stack
LeetCode Source

解題想法

這題主要解法透過判斷左邊和右邊 height 的大小來決定 res 能夠儲存多少單位

首先，我們必須過濾掉 len(height) < 3 的情況

再來透過兩個指標 left 和 right 來了解當前能夠儲存的位置

max_left 和 max_right 代表左右邊當前判斷到的最高值

過程中比較 max_left 和 max_right 來決定 left 和 right 更新與否

而 res 則依照最大值減當前偵測到的值來增加

之後便依照判斷是更新 left 或 right 位置

過程直到不符合 left < right 為止

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0

        res, left, right = 0, 0, len(height)-1
        max_left, max_right = height[left], height[right]

        while left < right:
            max_left = max(max_left, height[left])
            max_right = max(max_right, height[right])

            if max_left < max_right:
                res += max_left - height[left]
                left += 1
            else:
                res += max_right - height[right]
                right -= 1
        return res

C++

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() < 3)
            return 0;

        int left = 0, right = height.size()-1, res = 0;
        int max_left = height[left], max_right = height[right];
        while (left < right) {
            max_left = max(max_left, height[left]);
            max_right = max(max_right, height[right]);
            if (max_left < max_right) {
                res += max_left - height[left];
                left += 1;
            } else {
                res += max_right - height[right];
                right -= 1;
            }
        }
        return res;
    }
};

這系列文被記錄在 Top Interview 150 Series