双指针算法实战：快乐数与盛水最多容器解析

04. 盛水最多的容器

题目描述： 给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

暴力解法陷阱： 虽然可以用双重循环枚举所有组合，但时间复杂度是 O(n^2)，数据量大时会超时。我们需要更优的策略。

对撞指针策略： 设左右指针 left 和 right 分别指向数组首尾。容器的面积由宽度和较短边的高度决定： Area = min(height[left], height[right]) * (right - left)

为什么移动短边？ 假设当前左边界小于右边界。此时高度由左边决定。如果我们固定左边，移动右边，宽度减小，且新的高度受限于原来的短边（或更小），面积必然变小。所以，想要获得更大的面积，必须尝试移动那个限制高度的短边，看看能否遇到更高的柱子。

算法流程：

1. 初始化左右指针及最大面积变量。
2. 当 left < right 时循环：
   • 计算当前面积并更新最大值。
   • 比较两边高度，移动较短的一边指针。
3. 返回记录的最大面积。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int ret = 0;
        
        while (left < right) {
            // 计算当前容积
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            
            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ret;
    }
};

这两道题都是双指针的经典应用。快乐数侧重于利用快慢指针检测链表式循环，而盛水容器则展示了如何通过贪心策略配合对撞指针将复杂度从 O(n^2) 降至 O(n)。掌握这两种模式，能帮你快速解决大量类似的面试题型。