# 【LeetCode刷題】【演算法學習筆記】相向雙指針 接水桶
### 11. Container With Most Water
✎ 題目連結：[Leetcode](https://leetcode.com/problems/container-with-most-water/description/) / [力扣](https://leetcode.cn/problems/container-with-most-water/description/)

:::spoiler 💡思路
1. reference: [灵茶山艾府](https://leetcode.cn/problems/container-with-most-water/solutions/1974337/by-endlesscheng-f0xz/)
2. 說明: 目標是找出兩條垂直線組成的最大容器，使容器內的水最多。
3. 思路: 我們有一組數字 ==height==，代表不同位置的垂直線長度，每條線的 x 座標對應索引位置，而 y 座標則是 ==height[i]==。我們要找出兩條線，使它們與 x 軸組成的長方形面積最大。
我們這裡使用 雙指針法 **(Two Pointers)**，透過 **「從兩端向內移動」** 的方式，來找到最大的容器。
:::

class Solution:
    def maxArea(self, height: List[int]) -> int: # height 為高度
        # 初始化指針
        ans = left = 0 # 用來存儲目前找到的最大面積
        right = len(height) - 1

        while left < right:
            # 計算當前面積
            area = (right - left) * min(height[left], height[right])
            # 判斷當前最大面積
            ans = max(ans, area)

            # 移動指針
            # 誰短就移動誰
            # 因為總是移動 較短的那一邊，才有機會找到更大的面積
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        # 指針相遇，沒有區間可以形成容器，迴圈終止
        # ans 已經存下了過程中找到的最大面積
        return ans

### 42. Trapping Rain Water
---
✎ 題目連結：[Leetcode](https://leetcode.com/problems/trapping-rain-water/description/) / [力扣](https://leetcode.cn/problems/trapping-rain-water/description/)

:::spoiler 💡思路
1. reference: [灵茶山艾府](https://leetcode.cn/problems/trapping-rain-water/solutions/1974340/zuo-liao-nbian-huan-bu-hui-yi-ge-shi-pin-ukwm/)
2. 說明: 題目希望我們創建 程式碼目的是 **計算積水量**，也就是找出雨水可以存在哪些地方，並計算總共可以存多少水。目的是解決 接雨水（Trapping Rain Water） 的問題，也就是給定一個高度陣列 ==height==，求出凹槽中最多能接多少水。
3. 思路: 水的存量取決於 左邊最高的柱子 和 右邊最高的柱子 之間的最小值，減去當前柱子的高度。
:::
#### 寫法一: 前後綴分解

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height) # 柱子數

        preMax = [0] * n # preMax 記錄從最左邊數過來最大高度
        preMax[0] = height[0]
        # 拜訪最大高度
        for i in range(1, n):
            preMax[i] = max(preMax[i - 1], height[i]) # 確保 pre_max[i] 是前面最大柱子的高度

        # 計算每個位置的右邊最大值
        sufMax = [0] * n 
        sufMax[n-1] = height[n-1]
        for i in range(n-2, -1, -1): 
            sufMax[i] = max(sufMax[i + 1], height[i])

        # 計算每個位置能接的水量
        ans = 0
        for h, pre, suf in zip(height, preMax, sufMax): # 透過 zip() 來同時來拜訪三個參數
            ans += min(pre, suf) - h
        return ans

#### 寫法二: 相向雙指針
:::spoiler 💡思路
在一個地形 height 中，如果要存水，則該位置的水量取決於：

* 左邊最高的柱子
* 右邊最高的柱子
* 當前的柱子高度

水量計算公式：
水量 = **min(左邊最高柱子, 右邊最高柱子)−當前柱子高度**

我們使用 雙指針，從兩邊向中間移動，**動態計算水量**。
:::

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height) # 柱子數
        ans = left = preMax = sufMax = 0 # 變數初始化
        right = n - 1

        # 使用雙指針來計算水量
        while left < right:
            # 計算當前左右邊最高的柱子高度
            preMax = max(preMax, height[left])
            sufMax = max(sufMax, height[right])

            # 誰小誰先移動 因為最高的柱子無法接水 設為相遇位置
            # 水位由兩邊最高柱子相對低決定
            if preMax < sufMax: # 左柱較低
                ans += preMax - height[left]
                left += 1
            else:
                ans += sufMax - height[right]
                right -= 1
        return ans

#### 寫法三: 相向雙指針
:::spoiler 💡思路
* 這段程式碼的核心概念是「木桶效應」：某個位置能存多少水，取決於它左右兩側的最高柱子中較低的那個。
* 我們用 leftMax 和 rightMax 記錄當前遇到的最高柱子，確保我們能正確計算積水量。
:::

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        # 排除空柱子
        if not height:
            return 0

        # 初始化變數
        left, right = 0, len(height) - 1
        leftMax, rightMax = 0, 0
        waterTrapped = 0

        # 使用雙指針計算水量
        while left < right:
            # 如果右柱較高
            if height[left] < height[right]:
                # 較低的柱子 左柱決定水容量 計算加水量
                if height[left] >= leftMax: # 當前柱子大於等於左柱最高 不加水並更新左柱最高高度
                    leftMax = height[left]
                else: 
                    waterTrapped += leftMax - height[left]
                left += 1
            # 左柱較高 
            else:
                # 右柱當前高度 大於等於當前右柱最高
                if height[right] >= rightMax: # 更新右柱最高高度
                    rightMax = height[right]
                else: 
                    waterTrapped += rightMax - height[right] # 水漥低於水平面 可以容納水
                right -= 1

        return waterTrapped

:::spoiler **寫法二 v.s. 寫法三 效能比較**
**Code 1 比 Code 2 更快，原因如下：**

### **1. 變數更新次數**
- **Code 1:**
- 只更新 `preMax` 和 `sufMax` **一次**（每次迴圈只更新一次）。
- **Code 2:**
- `leftMax` 和 `rightMax` 在某些情況下會 **被重複賦值**（在 `if` 判斷中會多次賦值）。

### **2. 判斷條件更簡潔**
- **Code 1:**
- 直接比較 `preMax` 和 `sufMax`，避免了 `if height[left] < height[right]` 這種額外的條件判斷。
- **Code 2:**
- 內部有兩層 `if-else`，增加了額外的邏輯判斷，導致運算稍微變慢。

### **3. 指標移動效率**
- **Code 1:**
- 指標 `left` 和 `right` 只根據 `preMax < sufMax` 來移動，簡單且高效。
- **Code 2:**
- `left` 和 `right` 的移動依賴於 `height[left] < height[right]`，內部還有 `if height[left] >= leftMax` 的判斷，導致運算稍微變慢。

### **4. 總體比較**
| **比較項目** | **Code 1** | **Code 2** |
|------------|----------|----------|
| 變數更新次數 | 少 | 多 |
| 邏輯判斷次數 | 少 | 多 |
| 指標移動次數 | 少 | 稍多 |
| 效率 | 更快 | 稍慢 |

### **結論**
- **Code 1** 比 **Code 2** **更快**，因為：
- 變數更新次數較少。
- 判斷邏輯較少，減少 `if-else` 開銷。
- 指標移動規則更簡單，避免不必要的計算。

這使得 **Code 1 在實際執行時會略快於 Code 2** 🚀
:::