11. 盛最多水的容器

11. 盛最多水的容器

✨核心逻辑

本题采用 双指针(对撞指针) 的策略:

  1. 初始化指针:左指针 left 指向数组的最左端,右指针 right 指向数组的最右端,此时容器的宽度达到最大。
  2. 计算容积:容器能装水的容量由 左右指针指向的较短板高度两指针间的距离 决定,即 min(height[left], height[right]) * (right - left)
  3. 贪心移动:为了在宽度缩小时找到更大的容积,我们需要保留更高的边界。因此,如果左边的高度小于右边的高度,说明左边界是短板,移动右指针只会让高度变小(或不变),宽度必然变小,所以必须将左指针 left 向右移;反之,则将右指针 right 向左移。
  4. 记录最大值:在整个移动过程中,不断更新并记录出现过的最大容积 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 存储所有的单词,空间占用与单词总字符数成正比。

🔍总结一下:

起初,知道是双指针,但是无从下手,因为左右指针不知道怎么移动:移动其中一个就会导致宽度变短,而且短板长度也会变化,双重因素的变化让我无从下手

其实,这道题的精妙之处在于左右指针的移动是遵循一定的逻辑的: image-TSTO.png 所以我们只需要计算体积,比较并得到最大值,判断哪个是短板并移动即可!!