摘要
盛水最多的容器（Container With Most Water）是LeetCode上一道經典的算法題，考察對數組和雙指針技巧的應用。本文將詳細分析問題的核心思路，探討暴力法和雙指針法兩種實現方法，并對比它們的性能差異。通過代碼實現和復雜度分析，幫助深入理解如何高效解決此類問題。

---

問題描述

11. 盛最多水的容器

方法探討

方法一：暴力法（Brute Force）

思路

暴力法是最直接的思路：遍歷所有可能的線對組合，計算每對線構成的容器容量，記錄最大值。

代碼實現

public class Solution {public int maxAreaBruteForce(int[] height) {int maxArea = 0;for (int i = 0; i < height.length; i++) {for (int j = i + 1; j < height.length; j++) {int currentHeight = Math.min(height[i], height[j]);int currentWidth = j - i;maxArea = Math.max(maxArea, currentHeight * currentWidth);}}return maxArea;}
}

復雜度分析

• 時間復雜度：O(n2)，需要兩重循環遍歷所有可能的線對。
• 空間復雜度：O(1)，僅使用常數級額外空間。

缺點
當數組長度較大時（如 n=10^5），暴力法會超時，無法處理大規模數據。

---

方法二：雙指針法（Two Pointers）

思路

雙指針法通過一次遍歷高效解決問題，核心思想是縮減搜索空間：

1. 初始化指針：左指針 left 指向數組起始位置，右指針 right 指向數組末尾。
2. 計算容量：當前容量由 min(height[left], height[right]) * (right - left) 決定。
3. 移動指針：每次移動高度較小的指針（因為移動較高的指針不會增加容量）。
4. 更新最大值：比較并記錄最大容量。

正確性證明

假設當前左右指針高度分別為 h[left] 和 h[right]，且 h[left] < h[right]。此時若固定 left，無論 right 如何左移，新的容量一定小于當前容量（因為寬度減小，高度不超過 h[left]）。因此，必須移動左指針才有可能找到更大的容量。

代碼實現

public class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1;int maxArea = 0;while (left < right) {int currentHeight = Math.min(height[left], height[right]);int currentWidth = right - left;maxArea = Math.max(maxArea, currentHeight * currentWidth);// 移動較低的一側指針if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}
}

復雜度分析

• 時間復雜度：O(n)，只需一次遍歷。
• 空間復雜度：O(1)。

---

方法對比

方法	時間復雜度	空間復雜度	適用場景
暴力法	O(n2)	O(1)	小規模數據
雙指針法	O(n)	O(1)	大規模數據

---

總結

1. 暴力法雖然簡單直觀，但效率低下，僅適用于學習階段的小規模數據驗證。
2. 雙指針法通過縮小搜索空間將復雜度降至線性級別，是解決此問題的標準方法。
3. 關鍵思路：移動較低一側的指針，確保不會錯過更大容量的可能性。

拓展思考
雙指針法還可以用于解決其他類似問題，如“接雨水”（Trapping Rain Water） 從暴力到動態規劃再到雙指針：使用 Java 探索接雨水問題的不同解法。理解其核心思想有助于舉一反三，應對更多復雜場景。