[LeetCode] 42. Trapping Rain Water

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