#P4004. 盛最多水的容器
-
ID: 2206
Tried: 166
Accepted: 92
Difficulty: 4
盛最多水的容器
题目内容
给定一个长度为n的整数数组height 。有 n 条垂线，第 i 条线的两个端点是 (i,0) 和 (i,height[i]) 。
找出其中的两条线，使得它们与 x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明: 你不能倾斜容器。
输入描述
输出描述
样例1
输入
9
1 8 6 2 5 4 8 3 7
输出
49
说明
图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
样例2
输入
2
1 1
输出
1
提示
- n==height.length
- 2<=n<=105
- 0<=height[i]<=104
盛最多水的容器
题解思路
本题的目标是找到两条竖线，使得它们与x轴形成的容器能容纳最多的水。水的容量由 较短的竖线高度 和 两条竖线的横坐标距离 决定，即：
容积=min(height[left],height[right])×(right−left)
最直观的解法是 暴力枚举 两条竖线的所有可能组合，但时间复杂度为 O(n2)，会超时。
双指针优化
由于水的容量受限于 较短的竖线高度，我们可以使用 双指针法 来优化：
- 初始化：左右指针分别放在数组的最左和最右。
- 计算当前容积，记录最大值。
- 移动指针：
- 如果
height[left] < height[right]，移动左指针left++（因为容量受短板影响，试图寻找更高的左边界）。 - 否则，移动右指针
right--（寻找更高的右边界）。
- 如果
- 重复 直到
left == right。
这样，每个元素最多被访问一次，总时间复杂度为 O(n)，是最优解法。
复杂度分析
- 时间复杂度：O(n)，每个元素最多被访问一次。
- 空间复杂度：O(1)，只使用了常数级别的变量。
代码实现
Python 代码
class Solution:
def maxArea(self, height):
"""
双指针法求解最大容积
:param height: List[int] 代表垂线的高度数组
:return: int 最大水容量
"""
left, right = 0, len(height) - 1 # 初始化左右指针
max_area = 0 # 记录最大面积
while left < right:
# 计算当前区域的容量
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# 移动短板
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
# 读取输入
if __name__ == "__main__":
n = int(input()) # 读取整数 n
height = list(map(int, input().split())) # 读取数组
solution = Solution()
print(solution.maxArea(height))
Java 代码
import java.util.Scanner;
public class Main {
public class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
// 计算当前容积
int area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
// 移动较短的边
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取 n
int[] height = new int[n];
for (int i = 0; i < n; i++) {
height[i] = scanner.nextInt();
}
scanner.close();
Main main = new Main();
Solution solution = main.new Solution();
System.out.println(solution.maxArea(height));
}
}
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int maxArea = 0;
while (left < right) {
// 计算当前容积
int area = min(height[left], height[right]) * (right - left);
maxArea = max(maxArea, area);
// 移动较短的边
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
};
int main() {
int n;
cin >> n; // 读取 n
vector<int> height(n);
for (int i = 0; i < n; i++) {
cin >> height[i];
}
Solution solution;
cout << solution.maxArea(height) << endl;
return 0;
}