【算法日记 17】LeetCode 11. 盛最多水的容器：双指针与贪心思维的完美碰撞

📍 题目背景

今天我们来啃一块算法面试中的硬骨头，也是极其经典的双指针大题：[11. 盛最多水的容器]。 这道题的官方描述有很多“坐标轴”、“垂线”之类的数学术语，很多新手一看就晕了。但其实，我们完全可以把它当成一个“挑木板拼鱼缸”的游戏！

【大白话题目描述】给你一排高低不平的木板（数组height），让你从中挑出两块木板作为鱼缸的左右两面墙。 你的目标是：找出哪两块木板拼成的鱼缸，能装下最多的水！(注意：水能装多高，取决于两块木板中较矮的那一块，也就是著名的“木桶效应”。)

【示例】

输入:[1,8,6,2,5,4,8,3,7]输出:49解释:选高度为 8 和高度为 7 的两块木板，宽度为 7，高度取矮的 7，最大面积7 * 7 = 49。

✨ 核心破题逻辑：左右指针的“贪心博弈”

为了让鱼缸装最多的水，我们需要让宽度尽量大，同时高度也尽量高。 如果是暴力解法，两两组合去算面积，时间复杂度是 $O(N^2)$，在数据量大的时候必然会超时。

这就需要祭出我们的降维打击绝招：对撞双指针（左右指针）！

1. 初始状态：霸占最大宽度

我们让左指针left站在最左边，右指针right站在最右边。此时，鱼缸的宽度是最大的！算出一个初始面积，记录下来。

2. 灵魂拷问：接下来该挪哪块木板？

既然要往中间找，我们每一次只能移动一块木板。到底该挪高的那一块，还是矮的那一块？ 我们来推演一下：

• 如果挪动高的木板：宽度变小了。而水的高度永远受限于那块没动的“矮木板”。所以，不管新找的木板有多高，水位都不可能超过原来的矮木板。结论：挪高木板，面积一定会变小，纯属血亏！

• 如果挪动矮的木板：宽度虽然变小了，但是我们有可能遇到一块超级高的木板！这样一来，水位大幅提升，增加的高度完全可能弥补宽度的损失，从而创下面积新高！结论：挪矮木板，才有一线生机搏一把大的！

破题口诀：算完面积，谁矮，就无情地抛弃谁，让它往中间走一步寻找更高的木板！

💻 C++ 满分 AC 代码

掌握了上面的贪心逻辑，代码写起来简直行云流水，极其优雅：

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int maxArea(vector<int>& height) { // 🚀 绝招：左右指针 int left = 0; // 左边的木板 int right = height.size() - 1; // 右边的木板 int max_area = 0; // 记录历史最大水量 // 当两块木板还没有相遇的时候，不断往中间挤 while (left < right) { // 1. 算宽度 (下标相减) int width = right - left; // 2. 算高度 (木桶效应，取决于矮的那块) int current_height = min(height[left], height[right]); // 3. 算当前容量，并看看有没有破纪录 int current_area = width * current_height; max_area = max(max_area, current_area); // 4. 核心贪心抉择：抛弃矮木板，去寻找更高的！ if (height[left] < height[right]) { left++; // 左边矮，左边往右走一步寻找生机 } else { right--; // 右边矮，右边往左走一步寻找生机 } } return max_area; } };

🔍 复杂度深度剖析

• 时间复杂度：$O(N)$。双指针left和right分别从两头往中间走，每次循环必定会淘汰一块木板（移动一个指针）。当两个指针相遇时遍历结束，所以整个数组最多只会被扫描一次。这比 $O(N^2)$ 的暴力解法快了几个数量级！

• 空间复杂度：$O(1)$。我们只借用了left、right、max_area等几个整型变量来记录状态，完全没有开辟任何新的数组或哈希表空间，内存消耗做到了极致的精简。

💡 总结：这道题是“双指针”结合“贪心思想”的巅峰之作。它的精髓不在于代码有多复杂，而在于那个直击灵魂的数学逻辑——“在确定性（宽度缩小）中，去寻找唯一可能打破天花板的变量（抛弃短板）”。吃透这个逻辑，以后遇到类似求极值的问题，你都能一击必杀！