You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

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.

Understand

題目提供名為height的陣列，陣列長度為n，把每一個元素視為一個長條bar，value值為高度，要找出兩條線與 x 軸組成的容器中，能夠裝最多水的兩條bar並回傳最大容積值。

題目特別要求不能歪斜容器

水量的計算公式為

水量 = min(height(left_bar_index), height(right_bar_index)) * (right_bar_index - left_bar_index)

取兩條bar中最低那條作為水位，寬度為兩條bar的距離

right_bar_index 一定大於 left_bar_index，所以(right_bar_index - left_bar_index) >= 0

Happy Case

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
最佳選擇：index 1 (高度8) 和 index 8 (高度7)
水量 = min(8, 7) × (8 - 1) = 7 × 7 = 49

Edge Case

Match

題目要考的是 Two Pointer + 貪心演算法

將左右指針指向第一個元素與最後一個元素，每次左指針向右移 或 右指針向左移 都會減少寬度，在寬度減少的情況下，高度不增，容積會越來越小。

藉由比較兩指針的bar高度的大小，讓指向較低bar的指針移動，如此能找出當下的最大容積，而這個容積就是最優解。

🌟為什麼貪心演算法能在這題中找到全局的最優解?

這就要先說明 為什麼 height[left] < height[right]時要移動 left，而不是移動right?

我們已經知道left比right矮，若移動right向左，那麼寬度必定減少，在減少的情況下高度不變或變得更矮，容積必定越小，但若是移動後高度變高也無法讓容積變大，因為最低水位的高度已經被left決定了。

因此，當height[left] < height[right]時，left固定，所有left 與 right-1, right-2, right-3…的組合最大容積必定不變或變小，所以要移動left而不是right。

Plan

1. 建立兩個指針(left與right) 與 空數值變數max_acc用來儲存當下最大容積值
2. left指針位於第一個元素，right指針位於最後一個元素，所以兩個指針的值必定是 left < right，如果指針重疊了或left>right就代表已經遍歷過所有可能是最優解的組合
3. 計算當下容積，如果當下容積>當下紀錄的最大值(max_acc)，就取代
4. 比較兩個指針指向的Bar的高度
   • 如果left指針指向的Bar高度較小，則left向右移
   • 如果right指針指向的Bar高度較小，則right向左移
5. 回到步驟2

Implement

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height)-1
    max_acc = 0

    while left < right:
        curr_acc = min(height[left], height[right]) * (right - left)
        if curr_acc > max_acc:
            max_acc = curr_acc

        if height[left] > height[right]:
            right -= 1
        else:
            left += 1

    return max_acc

Reviews

happy case

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

edge case

• height = [1, 2]:

  left=0, right=1 → min(1,2)×1 = 1 → right -= 1，right變成0，與left重疊跳出迴圈

• height = [5, 5, 5, 5]

  回合數	說明	output
  1	min(5,5)×3=15	15
  2	min(5,5)×2=10	10
  3	min(5,5)×1=5	5

Evaluate