给定一个长度为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
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
解题思路:
(1)决定水槽容量的有宽度和最低的一侧
(2)当移动较长板时,较短板不变或者变小。移动较短板时,较短板可能变大变小或者不变。于是发现移动较短板的时候,有可能提高水槽的容量。
(3)下面需要考虑宽度的因素,如果可以让宽度每次变化一定,那么就可以用(2)来判断水槽容量的变化情况。
(4)于是采用双指针分别指向height的最右边和最左边,这样不管移动长板还是短板,宽度一定减小,结合(2),移动长板一定会导致水槽容量变小。
算法:
(1)双指针指向height左边和右边
(2)计算当前水槽容量,更新最大值
(3)移动短板指针,如果左右指针未相遇回到第(2)步,否则结束。
源代码:
int maxArea(vector<int>& height) {
int l=0,r=height.size()-1;
int max=0;
while (l!=r){
int temp=(r-l)*min(height[l],height[r]);
if (temp > max) max=temp;
height[l]<height[r] ? ++l : --r;
}
return max;
}