一魚多吃 用水槽模型 解 最多的雨水儲存量 Trapping Rain Water Leetcode #42

這題的題目在這裡:

題目敘述

題目會給我們一個陣列，陣列裡面每個數字分別代表高低各不同的隔板高度，問我們從降雨之後，最多可以儲存多少水量?

測試範例

Example 1:

範例一的圖解

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
藍色部分的方格，代表可以儲存雨水的格子點。​

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

約束條件

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

演算法

其實這一題和前面學過的水槽模型裝水那一題九成像。

都是給我們隔板高度，要求我們計算最多可以儲存的水量是多少?

差別在於:

前一題的水槽底部是平的。

這一題的水槽底部高低不同，有凹有凸。

但是，最關鍵的核心精神相同，可以裝的水量多寡由比較矮的隔板決定。

(因為水只要超過比較矮的那一邊就會溢出去，就算再下雨注入水也
無法儲存更多了。)

因此，我們只要建立一個滑窗，每次在水平方向移動一格，收縮比較矮的一邊，

如果左邊的隔板比右邊矮，就收縮左邊。

如果右邊的隔板比左邊矮，就收縮右邊。

每次迭代的時候，同步更新累加
當下可以儲存的水量 = 比較矮的隔板高度 - 水槽底部高度
(相當於二維平面上投影的面積，就像範例圖中的樣子)

最後，回傳能儲存雨水的總面積，就是答案。

程式碼

class Solution:
　def trap(self, height: List[int]) -> int:
　　
　　if len(height) < 3:
　　　
　　　# Quick response for impossible cases
　　　return 0
　　
　　volume, size = 0, len(height)
　　
　　# two pointers, initialized as boundary index
　　left, right = 0, size-1
　　
　　# local max height on two sides
　　left_wall_max, right_wall_max = height[left], height[right]
　　
　　# scan each index with two-pointers
　　while left < right:
　　　
　　　# update local max height
　　　left_wall_max, right_wall_max = max(height[left], left_wall_max), max(height[right], right_wall_max)
　　　
　　　
　　　if left_wall_max <= right_wall_max:
　　　　
　　　　# left wall is shorter than right wall
　　　　
　　　　# update trapping rain water of current index
　　　　volume += left_wall_max - height[left]
　　　　
　　　　# move left pointer to right hand side
　　　　left += 1
　　　　
　　　else:
　　　　
　　　　# right wall is shorter than left wall
　　　　
　　　　# update trapping rain water of current index
　　　　volume += right_wall_max - height[right]
　　　　
　　　　# move right pointer to left hand side
　　　　right -= 1
　　　　
　　
　　return volume

複雜度分析

時間複雜度:

O( n ) 收縮滑窗，滑窗寬度從n-1 收縮到 1，總共耗費O(n)的時間

空間複雜度:

O(1) 都是臨時變數，所占用的記憶體空間固定，都是常數級別O(1)

關鍵知識點

這一題用到的也是水槽裝水的模型，唯一的小差別就是多了水槽底部有了高度，但是核心精神不變: 可以裝的水量多寡由比較矮的隔板決定。

強烈建議複習Container With Most Water這一題，
鞏固 水槽裝水的模型 與 雙指針應用的知識點

Reference:

[1] Python O(n) by two-pointers // DP [w/ Hint] - Trapping Rain Water - LeetCode