11. 盛最多水的容器
✨核心逻辑
本题采用 双指针(对撞指针) 的策略:
- 初始化指针:左指针
left指向数组的最左端,右指针right指向数组的最右端,此时容器的宽度达到最大。 - 计算容积:容器能装水的容量由 左右指针指向的较短板高度 和 两指针间的距离 决定,即
min(height[left], height[right]) * (right - left)。 - 贪心移动:为了在宽度缩小时找到更大的容积,我们需要保留更高的边界。因此,如果左边的高度小于右边的高度,说明左边界是短板,移动右指针只会让高度变小(或不变),宽度必然变小,所以必须将左指针
left向右移;反之,则将右指针right向左移。 - 记录最大值:在整个移动过程中,不断更新并记录出现过的最大容积
maxArea。
🔥代码实现(含详细变量注释)
class Solution {
public int maxArea(int[] height) {
// left:左指针,初始指向数组的第一个下标
int left = 0;
// right:右指针,初始指向数组的最后一个下标
int right = height.length - 1;
// maxArea:用于记录当前遍历过程中找到的最大容器可容纳的水量
int maxArea = 0;
// 当左指针小于右指针时,说明还存在合法的容器区间,继续循环
while (left < right) {
// currentV:计算当前左右指针构成的容器能容纳的水量
// 水量 = 左右指针指向的较短板高度 * 两指针之间的距离
int currentV = Math.min(height[left], height[right]) * (right - left);
// 更新最大水量,保留历史最大值
maxArea = Math.max(maxArea, currentV);
// 如果左边的板子比右边矮,说明左边界是限制容量的“短板”
// 为了获取更大容积,必须放弃当前的短板,尝试寻找更高的左边界,因此左指针向右移动
if (height[left] < height[right]) {
left++;
} else {
// 反之,如果右边的板子是短板(或者两块板等高),则右指针向左移动
right--;
}
}
// 遍历结束后,返回记录的最大水量
return maxArea;
}
}
- ⏱️复杂度分析
时间复杂度:O(N),只需要对字符串中的每个字符进行一次遍历和入队出队操作
空间复杂度:O(N),额外使用了双端队列 deque 存储所有的单词,空间占用与单词总字符数成正比。
🔍总结一下:
起初,知道是双指针,但是无从下手,因为左右指针不知道怎么移动:移动其中一个就会导致宽度变短,而且短板长度也会变化,双重因素的变化让我无从下手
其实,这道题的精妙之处在于左右指针的移动是遵循一定的逻辑的:
所以我们只需要计算体积,比较并得到最大值,判断哪个是短板并移动即可!!
所以我们只需要计算体积,比较并得到最大值,判断哪个是短板并移动即可!!