LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.08
• 题目：11. 盛最多水的容器
• 难度：中等
• 标签：数组、双指针、贪心

1. 题目理解

问题描述： 给定一个长度为 n 的整数数组 height，其中 height[i] 表示第 i 个竖线的高度。 找出两条竖线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 不能倾斜容器。

示例：

输入：height = [1,8,6,2,5,4,8,3,7] 输出：49

2. 解题思路

核心观察

• 容量由两个因素决定：两线间距（宽度）和两线中较矮的高度（高度）。
• 公式：容量 = 宽度 × 较小高度。
• 双指针贪心：初始时左右指针在两端（宽度最大），每次移动较矮的一侧指针，试图寻找更高的线来增大容量。

算法步骤

1. 左指针指向开头，右指针指向末尾。
2. 计算当前指针构成的容器容量，更新最大值。
3. 移动高度较小的那个指针。
4. 重复直到指针相遇。

3. 代码实现

package lc0_lc99.lc11;

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int leftPos = 0;
        int rightPos = height.length - 1;
        while (leftPos < rightPos) {
            max = Math.max(Math.min(height[leftPos], height[rightPos])*(rightPos-leftPos), max);
            if (height[leftPos]>height[rightPos]){
                rightPos--;
            }
            else {
                leftPos++;
            }
        }
        return max;
    }
}

4. 代码优化说明

class Solution {
public int maxArea(int[] height) {
int left=0;
int right=height.length-1;
int max=0;
while(left<right){
    // 计算当前有效高度
int h=Math.min(height[left],height[right]);
    // 更新最大容量
max=Math.max(max,h*(right-left));
    // 跳过所有比当前高度小的左边界（剪枝）
while(left<right&&height[left]<=h) left++;
    // 跳过所有比当前高度小的右边界（剪枝）
while(left<right&&height[right]<=h) right--;
}
return max;
}
}

5. 复杂度分析

• 基础双指针版
  • 时间复杂度：$O(n)$，一次遍历。
  • 空间复杂度：$O(1)$，仅用常数变量。
• 优化剪枝版
  • 时间复杂度：仍为 $O(n)$，但实际迭代次数更少，跳过无效指针移动。
  • 空间复杂度：$O(1)$。

6. 总结

• 核心：双指针 + 贪心，每次移动矮边，保证不丢失最优解。
• 优化点：连续跳过比当前高度小的无效指针，减少循环次数，无多余 if 判断。
• 关键：容量由短板决定，移动短板才可能变大，移动长板一定变小。