讓水槽裝最多的水 Container With Most Water_Leetcode 精選75題
題目敘述
題目會給我們一個隔板陣列height，代表每個隔板的高度，讓我們選取兩個隔板作為水槽的邊界，請問最多我們能裝多少水?
測試範例
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
約束條件
Constraints:
n == height.length
n代表輸入陣列height的長度。
2 <= n <= 10^5
height陣列長度介於2~10^5之間。
0 <= height[i] <= 10^4
每片隔板的高度介於0~10^4之間。
演算法
除了第一直覺的雙層暴力法(很有可能time-out 超過平台限制)之外，還有一個優雅的雙指針two-pointers的解法。
關鍵在於，存水的關鍵，在於左、右兩邊的隔板，哪邊比較矮，矮的隔板決定了能存多少水。
舉例來說: 假如底是w，左邊隔板高度是5，右邊的隔板高度是7，那麼可以儲存的水量就是w*(5,7) = 5w，因為，任何高度超過比較矮隔板的水流，最終都會溢流出去。
示意圖
image.png
image.png
因此，我們可以建造一個two pointers雙指針的迭代演算法。
令area = 橫截面面積 代表 儲水量的最大值，初始化為0
接著，left左指針初始化為0，代表最左邊的隔板index；right右指針初始化為n-1，代表最右邊的隔板。
每一回合迭代，就比較height[left], height[right]哪邊比較矮。
矮隔板的高度 * 當下的底
= 矮隔板的高度 * width
= 矮隔板的高度 * (right-left)
= 當下可以儲存的水量。假如比原本的儲水量還多，就更新為最大值。
然後，矮的那端往內收縮一格，假如右邊的隔板比較矮，就收縮右邊。同理，假如左邊的隔板比較矮，就收縮左邊。
如此反覆進行迭代，迴圈結束時，area 就代表整體儲水量的最大值。
程式碼
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
left, right = 0, n-1
area = 0
for width in range(n-1, 0, -1):
if height[left] < height[right]:
area = max( area, width * height[left] )
left += 1
else:
area = max( area, width * height[right] )
right -= 1
return area
關鍵知識點
在於察覺存水多寡的關鍵，在於左、右兩邊的隔板，哪邊比較矮，
矮的隔板決定了能存多少水。
複雜度分析
時間複雜度:
雙指針從頭尾兩端向中間收縮，所需時間為O(n)
空間複雜度:
只有使用到固定大小的臨時變數，所需空間為O(1)常數級別。
Reference:
