主題: 學習筆記
LeetCode 11：TypeScript 盛最多水的容器，為什麼要移動較矮的那端
保留我的雙指標解法，補上暴力解對照、捨棄較矮端點的正確性證明，以及 O(n) 時間與 O(1) 空間分析。
我的解法是先把指標放在陣列兩端，從最寬的容器開始算。每次記錄面積，再把較矮那端往內移。這篇保留我寫的程式，另外補上暴力解、正確性證明與可執行測試。
題目與面積
LeetCode 11：Container With Most Water 給定非負整數陣列 height。位置 i 有一條高度為 height[i] 的垂直線，選兩條線與水平軸形成容器，回傳最大盛水面積。容器不能傾斜。
題目限制為 2 <= height.length <= 100000、0 <= height[i] <= 10000。選擇位置 left、right 時，寬度是索引差，高度取兩條線中較短的一條：
area = Math.min(height[left], height[right]) * (right - left)
中間的線不需要扣除體積。這題只看選定的兩個邊界，不是在計算每個凹槽能接多少雨水。
我寫的雙指標解法
function maxArea(height: number[]): number {
let p1 = 0;
let p2 = height.length - 1;
let max = 0
while (p2 > p1) {
const currentArea = Math.min(height[p1], height[p2]) * (p2 - p1)
max = Math.max(max, currentArea)
if (height[p1] < height[p2]) {
p1++;
} else {
p2--;
}
}
return max
};p1 從左、p2 從右開始。每輪先計算目前面積，更新 max，接著依兩端高度決定移動哪個指標。兩端同高時，這份程式會移動右端。
這份實作已達到線性時間與常數額外空間。下面補充的內容著重在為什麼這樣移動是安全的，演算法不需要換掉。
補充對照：枚舉所有配對
以下是整理文章時補充的暴力解，並非我原本提交的版本。
function maxAreaBruteForce(height: number[]): number {
let max = 0;
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
}
}
return max;
}兩個不同位置共有 n * (n - 1) / 2 種配對。逐一計算需要 O(n²) 時間、O(1) 額外空間。當長度為 100000，配對數是 4,999,950,000。雙指標省下的就是那些可以證明不會更好的配對。
為什麼能捨棄較矮那端
假設目前 height[left] <= height[right]，面積就是：
height[left] * (right - left)
現在固定左端，改選任何位於兩端之間的右端 j。新容器的高度最多仍是 height[left]，寬度則縮成 j - left。因此：
min(height[left], height[j]) * (j - left) <= height[left] * (right - left)
目前這組已經計算並存入最大值，所以剩下所有「固定這個左端」的配對都不必再試，可以直接移動左端。右端較矮時，理由完全對稱。
例如兩端高度為 2 與 8，距離是 5，面積為 10。固定高度 2 的左端，右端往內移一格，即使找到高度 100，面積也最多只有 8。移動較矮端提供了提高高度上限的機會，但不保證下一輪面積一定變大，所以仍要保留歷史最大值。
若兩端一樣高，捨棄任一端都成立。原本程式把相等情況放在 else，因此移動右端，沒有問題。
迴圈不變量
每輪開始時，max 保存已檢查配對的最大面積；所有已排除的配對都不可能超過 max。仍可能改善答案的配對，其兩個端點都留在 [p1, p2] 裡。
初始時還沒有排除任何配對，這個條件成立。每輪先更新最大值，再利用前面的不等式排除較矮端點，條件繼續成立。指標相遇後，區間內不再有兩個不同端點，所有候選都已檢查或排除，max 就是答案。
時間與額外空間
令 n = height.length。兩個指標的距離一開始是 n - 1，每輪恰好縮小 1，因此迴圈執行 n - 1 次，時間為 O(n)。
程式只有幾個數字變數，沒有建立隨輸入增長的陣列或 Map，額外空間為 O(1)。原本的 height 不計入額外空間，程式也不修改它。
補充驗證
前三個案例來自我的解答，以下把預期結果改成可執行 assertions，並補上零高度、同高、遞增與輸入不變的檢查。將程式與測試放進同一個 TypeScript 檔，在支援執行 TypeScript 的環境執行即可。
import assert from "node:assert/strict";
assert.equal(maxArea([1, 7, 6, 2, 5, 4, 8, 3, 8]), 49);
assert.equal(maxArea([1, 1]), 1);
assert.equal(maxArea([8, 7, 2, 1]), 7);
assert.equal(maxArea([0, 0]), 0);
assert.equal(maxArea([4, 4, 4, 4]), 12);
assert.equal(maxArea([1, 2, 3, 4]), 4);
assert.equal(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
const original = [1, 7, 6, 2, 5, 4, 8, 3, 8];
const snapshot = [...original];
maxArea(original);
assert.deepEqual(original, snapshot);第一組自訂資料使用索引 1 與 8，高度分別為 7 與 8，面積為 7 * 7 = 49。它與官方範例的陣列不同，只是答案同樣為 49。[8, 7, 2, 1] 的最佳組合是索引 0 與 1，面積為 7。
整理時另枚舉長度 2 到 7、每個高度為 0 到 3 的全部 21,840 組陣列，雙指標與暴力解結果一致。這個檢查可以找實作錯誤，完整正確性仍由前面的排除論證說明。
常見陷阱與下次能用的想法
寬度是 p2 - p1，不是包含端點的元素數量，所以不能加 1。計算面積與更新最大值必須在移動指標之前完成；也不能先排序，因為排序會改變原本的位置距離。
這題讓雙指標的移動規則有了可以說清楚的理由。下次遇到縮小搜尋區間的題目，可以先問自己：這次捨棄的候選，為什麼確定不會比已經看過的結果更好？