LeetCode 11: Container With Most Water (Two Pointers)
LeetCode 11Two PointersGreedyInterviewToday we solve LeetCode 11 - Container With Most Water.
Source: https://leetcode.com/problems/container-with-most-water/
English
Problem Summary
Given an array height, each value is the height of a vertical line at index i. Pick two lines that, with the x-axis, form a container. Return the maximum water area.
Area formula: (right - left) * min(height[left], height[right]).
Key Insight
The width is determined by distance between pointers, while the effective height is the shorter side. If we keep the shorter side and move the taller side inward, width shrinks and the bottleneck height does not improve, so area cannot get better systematically.
Therefore, always move the pointer at the shorter height. This is the core correctness idea.
Brute Force and Why Insufficient
Brute force tries every pair (i, j), computes each area, and tracks max. That is O(n^2) time and O(1) space. It is straightforward but too slow for large input sizes.
Optimal Algorithm (Step-by-Step)
1) Initialize left = 0, right = n - 1, best = 0.
2) While left < right:
a) Compute width = right - left.
b) Compute h = min(height[left], height[right]).
c) Update best = max(best, width * h).
d) If height[left] <= height[right], increment left; else decrement right.
3) Return best.
Why it works: each move discards only states that cannot beat current bottleneck logic, and eventually covers all potentially optimal boundaries in linear time.
Complexity Analysis
Time: O(n) (each pointer moves at most n times).
Space: O(1) extra.
Common Pitfalls
- Moving the taller pointer first (breaks greedy logic).
- Forgetting min(...) in area formula.
- Integer overflow in some languages if constraints were larger (use 64-bit when needed).
- Off-by-one loop condition: must be left < right.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int best = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
int area = (right - left) * h;
best = Math.max(best, area);
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return best;
}
}func maxArea(height []int) int {
left, right := 0, len(height)-1
best := 0
for left < right {
h := height[left]
if height[right] < h {
h = height[right]
}
area := (right - left) * h
if area > best {
best = area
}
if height[left] <= height[right] {
left++
} else {
right--
}
}
return best
}class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = (int)height.size() - 1;
int best = 0;
while (left < right) {
int h = min(height[left], height[right]);
int area = (right - left) * h;
best = max(best, area);
if (height[left] <= height[right]) {
++left;
} else {
--right;
}
}
return best;
}
};class Solution:
def maxArea(self, height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = (right - left) * h
best = max(best, area)
if height[left] <= height[right]:
left += 1
else:
right -= 1
return bestvar maxArea = function(height) {
let left = 0, right = height.length - 1;
let best = 0;
while (left < right) {
const h = Math.min(height[left], height[right]);
const area = (right - left) * h;
if (area > best) best = area;
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return best;
};中文
题目概述
给定数组 height，第 i 个值表示在坐标 i 处的一条竖线高度。选择两条线与 x 轴围成容器，求最多能装多少水。
面积公式：(right - left) * min(height[left], height[right])。
核心思路
容器高度由较短那条边决定，宽度由两指针距离决定。每次移动指针都会让宽度变小，所以只有在“可能提高短板高度”时才值得移动。也就是说：应移动较短边对应的指针。
如果反过来移动较高边，短板不变、宽度还缩小，几乎不可能得到更优解。
暴力解法与不足
暴力法枚举所有下标对 (i, j) 并计算面积，时间复杂度 O(n^2)，空间复杂度 O(1)。思路直观，但在大输入下性能不足。
最优算法（步骤）
1）初始化：left = 0，right = n - 1，best = 0。
2）当 left < right 时循环：
a）计算宽度 width = right - left；
b）计算有效高度 h = min(height[left], height[right])；
c）更新答案 best = max(best, width * h)；
d）若 height[left] <= height[right] 则 left++，否则 right--。
3）循环结束返回 best。
本质上是“缩窗口 + 保留潜在最优边界”的贪心双指针。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 先移动较高边，导致错过最优。
- 面积公式误写成 max(height[left], height[right])。
- 循环条件写成 left <= right 引发边界问题。
- 某些语言中若数据范围更大，应考虑使用 64 位整数。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int best = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
int area = (right - left) * h;
best = Math.max(best, area);
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return best;
}
}func maxArea(height []int) int {
left, right := 0, len(height)-1
best := 0
for left < right {
h := height[left]
if height[right] < h {
h = height[right]
}
area := (right - left) * h
if area > best {
best = area
}
if height[left] <= height[right] {
left++
} else {
right--
}
}
return best
}class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = (int)height.size() - 1;
int best = 0;
while (left < right) {
int h = min(height[left], height[right]);
int area = (right - left) * h;
best = max(best, area);
if (height[left] <= height[right]) {
++left;
} else {
--right;
}
}
return best;
}
};class Solution:
def maxArea(self, height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = (right - left) * h
best = max(best, area)
if height[left] <= height[right]:
left += 1
else:
right -= 1
return bestvar maxArea = function(height) {
let left = 0, right = height.length - 1;
let best = 0;
while (left < right) {
const h = Math.min(height[left], height[right]);
const area = (right - left) * h;
if (area > best) best = area;
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return best;
};
Comments