您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

LeetCode 011 盛最多水的容器：雙指鈍優化解法與圖解分析

編輯：Java 綜合教學

題目描述

給定 n 個非負整數 a1, a2, ..., an，每個數代表坐標點 (i, ai)。繪製 n 條垂直線，線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中兩條線，使其與 x 軸共同構成的容器能容納最多的水。容器不能傾斜。

難度：Medium
核心公式：面積 = 底 (索引差) × 高 (兩線較短者)

思路演進：從暴力到優化

方法一：暴力雙層循環 O(n²)

遍歷所有線對組合，計算面積，記錄最大值。簡單但超時。

方法二：優化雙層循環 + 反向遍歷剪枝

觀察：內層循環反向遍歷時，底 (j - i) 單調遞減。若當前高度 min(h[i], h[j]) ≤ 歷史最大高度，則面積必然 ≤ 歷史最大面積，可直接 break 進入下一輪外層循環。

方法三：雙指針法 O(n) —— 最優解

核心洞察：面積受限於較短板。移動較長板，底減少且高不增（仍受限於短板），面積必減；只有移動較短板，才有機會獲得更高的板從而增加面積。

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        
        // 移動較短板
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

原文優化解法分析（反向遍歷剪枝版）

原文提供了一種介於暴力與雙指針之間的優化：

private static int[] method(int[] array) {
    int[] result = new int[2];
    int maxArea = 0;
    for (int i = 0; i < array.length; i++) {
        int maxHeight = 0;
        // 反向遍歷：底 (j-i) 遞減
        for (int j = array.length - 1; j > i; j--) {
            int height = Math.min(array[i], array[j]);
            // 剪枝：只有高度超過歷史最大高度，才有可能產生更大面積
            if (height > maxHeight) {
                maxHeight = height; // 先更新最大高度
                if (height * (j - i) > maxArea) {
                    maxArea = height * (j - i);
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
    }
    return result;
}

關鍵點解析

maxHeight 初始化在內層循環外，每輪外層循環重置
反向遍歷保證底單調遞減，高度不增則面積必減，果斷剪枝
時間複雜度：最好 O(n)（遞增數組），最壞 O(n²)（遞減數組），平均優於暴力

測試驗證

public static void main(String[] args) {
    int[] height = {1,8,6,2,5,4,8,3,7};
    System.out.println("雙指針結果: " + maxArea(height)); // 49
    System.out.println("剪枝版結果: " + Arrays.toString(method(height))); // [1, 8] 索引對應值 8 和 7
}