【算法日记 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(vectorint 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等几个整型变量来记录状态完全没有开辟任何新的数组或哈希表空间内存消耗做到了极致的精简。 总结这道题是“双指针”结合“贪心思想”的巅峰之作。它的精髓不在于代码有多复杂而在于那个直击灵魂的数学逻辑——“在确定性宽度缩小中去寻找唯一可能打破天花板的变量抛弃短板”。吃透这个逻辑以后遇到类似求极值的问题你都能一击必杀