一、题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
二、测试用例
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
三、解题思路
- 基本思路:
双指针,从最长宽度一直收缩,记录下最大容积。 - 具体思路:
- 预处理:定义头指针 i 和尾指针 j ,初始化为 0 和 n-1 。定义 max_capacity ,表示最大容量,初始化为 0 。
- 遍历:因为刚开始是最大宽度,高度不确定,要想增大容积,只能增加高度,所以头指针和尾指针比较,小的那个进行移动,以寻找更高的高度。在寻找期间,不断比较容积,记录下最大的那个。
四、参考代码
时间复杂度:
O
(
n
)
\Omicron(n)
O(n)
空间复杂度:
O
(
1
)
\Omicron(1)
O(1)
class Solution {
public:
int maxArea(vector<int>& height) {
int n=height.size();
int i=0,j=n-1;
int max_capacity=0;
while(i<j){
max_capacity=max((j-i)*min(height[i],height[j]),max_capacity);
if(height[i]<height[j])
i++;
else
j--;
}
return max_capacity;
}
};
标签:11,容器,capacity,int,max,height,力扣,最多水,指针
From: https://blog.csdn.net/yyh520025/article/details/141224816