【Hot 100 刷题计划】 LeetCode 11. 盛最多水的容器 | C++ 双指针题解

LeetCode 11. 盛最多水的容器 | C 双指针贪心最优解 题目描述题目级别中等给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。 解题思路双指针 贪心策略这道题的直观解法是两层for循环暴力枚举所有组合但时间复杂度会高达O(N2)O(N^2)O(N2)必然超时。想要将时间复杂度优化到O(N)O(N)O(N)我们需要借助双指针和木桶效应的贪心思想。1. 核心公式与木桶效应容器的盛水量由两个因素决定盛水量 两条垂线之间的距离 (宽)×\times×两条垂线中较短的那条 (高)这就是著名的“木桶效应”一只水桶能装多少水取决于它最短的那块木板。2. 双指针的移动逻辑灵魂所在我们在数组的两端各放置一个指针左指针l指向开头右指针r指向结尾。此时容器的宽度是最大的。接下来我们需要不断向内收缩窗口移动指针。那到底该移动左指针还是右指针呢假设当前左边界较低height[l] height[r]如果移动高板右指针r--容器的宽度一定会变小而容器的最高限制依然是原来的低板height[l]甚至新板比它还低。因此移动高板盛水量一定变小或不变绝不可能变大如果移动低板左指针l虽然容器的宽度变小了但我们有可能会遇到一块极高的板子使得容器的短板变长。因此移动低板盛水量是有可能变大的结论每次比较两个指针指向的垂线谁短就移动谁直到两个指针相遇。在这个过程中不断刷新记录的最大盛水量res即可。 C 代码实现classSolution{public:intmaxArea(vectorintheight){// 定义左右双指针分别指向数组的两端intl0;intrheight.size()-1;// res 用于记录全局最大盛水量intres0;// 当两指针相遇时结束循环while(lr){// 计算当前左右指针构成的容器容量并刷新最大值// 容量 宽度 (r - l) * 高度 (左右两板中的较短者)resmax(res,(r-l)*min(height[l],height[r]));// 贪心策略移动较短的那块板寻找变大的可能性if(height[l]height[r]){l;// 左板短左指针右移}else{r--;// 右板短右指针左移}}returnres;}};