每日算法 — 使用java实现盛最多水：双指针收敛与面积最大化策略

算法背景

盛最多水的容器是LeetCode 11题，问题描述为：给定n个非负整数表示容器宽度为1的直方图高度，找出两条线使得与x轴构成的容器能盛最多的水。该问题虽然描述简单，却是理解双指针收敛策略的经典范例——如何从O(n²)的暴力解法优雅地优化到O(n)的双指针解法，其背后的贪心正确性证明极具启发性。

核心思路

暴力解法：枚举所有左右边界组合，计算面积取最大值。时间O(n²)，空间O(1)。

双指针优化：
– 初始化左右指针分别在数组两端
– 计算当前面积：area = min(height[left], height[right]) × (right - left)
– 关键决策：移动较短边的指针向内收敛

正确性证明：为什么移动短边？
– 当前面积由 min(h[l], h[r]) × width 决定
– 如果移动长边，宽度减小，高度最多不变（仍受短边限制），面积必然减小
– 如果移动短边，虽然宽度也减小，但高度可能增加，存在面积变大的可能
– 因此移动短边是唯一能”探索更大面积可能”的决策

完整Java实现

/**
 * 盛最多水的容器 - 双指针面积最大化
 * 时间复杂度: O(n)  空间复杂度: O(1)
 */
public class ContainerWithMostWater {

    /**
     * 核心算法：双指针收敛
     */
    public int maxArea(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }

        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // 计算当前面积
            int currentHeight = Math.min(height[left], height[right]);
            int currentWidth = right - left;
            int currentArea = currentHeight * currentWidth;
            maxArea = Math.max(maxArea, currentArea);

            // 移动较短边的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }

    /**
     * 优化版本：跳过高度相同的连续位置
     */
    public int maxAreaOptimized(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, h * (right - left));

            // 移动短边，并跳过所有不高于当前高度的位置
            if (height[left] < height[right]) {
                int currentLeft = height[left];
                while (left < right && height[left] <= currentLeft) {
                    left++;
                }
            } else {
                int currentRight = height[right];
                while (left < right && height[right] <= currentRight) {
                    right--;
                }
            }
        }

        return maxArea;
    }

    /**
     * 记录具体是哪两条边构成最大面积
     */
    public int[] maxAreaWithIndices(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        int bestLeft = 0, bestRight = 0;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = h * (right - left);

            if (area > maxArea) {
                maxArea = area;
                bestLeft = left;
                bestRight = right;
            }

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return new int[]{bestLeft, bestRight, maxArea};
    }

    /**
     * 进阶问题：接雨水（二维扩展）
     * 每个位置能接的雨水 = min(左边最高, 右边最高) - 当前高度
     */
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }

        return water;
    }

    /**
     * 暴力解法 - 用于对比验证
     */
    public int maxAreaBruteForce(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                max = Math.max(max, area);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        ContainerWithMostWater solution = new ContainerWithMostWater();

        // 测试用例1: 基本场景
        int[] height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("高度数组: [1,8,6,2,5,4,8,3,7]");
        System.out.println("最大面积: " + solution.maxArea(height1));
        int[] result = solution.maxAreaWithIndices(height1);
        System.out.println("最优边界: [" + result[0] + ", " + result[1] + "], 面积=" + result[2]);

        // 测试用例2: 单调递增
        int[] height2 = {1, 2, 3, 4, 5};
        System.out.println("\n高度数组: [1,2,3,4,5]");
        System.out.println("最大面积: " + solution.maxArea(height2));

        // 测试用例3: 接雨水
        int[] height3 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("\n接雨水数组: [0,1,0,2,1,0,1,3,2,1,2,1]");
        System.out.println("可接雨水: " + solution.trap(height3));

        // 验证双指针与暴力法结果一致
        System.out.println("\n双指针 vs 暴力法验证: " +
            (solution.maxArea(height1) == solution.maxAreaBruteForce(height1) ? "通过" : "失败"));
    }
}

复杂度分析

关键洞察：双指针法每个位置最多被访问一次，n个位置共n-1次比较，相比暴力的O(n²)是质的飞跃。

扩展思考

1. 三维扩展：如果是三维容器（宽度×深度×高度），问题会变为寻找最大体积，复杂度会显著提升。
2. 多个容器：如果要求找出k个不重叠容器的最大总容量，需要结合动态规划。
3. 动态高度：如果高度随时间变化（如降雨），需要在线算法处理。