难度中等3493
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
代码语言：javascript复制class Solution {
public:
int maxArea(vector<int>& height) {
}
};这里用到了动态规划，基本的表达式: area = min(height[i], height[j]) * (j - i) 使用两个指针，值小的指针向内移动，这样就减小了搜索空间 因为面积取决于指针的距离与值小的值乘积，如果值大的值向内移动，距离一定减小，而求面积的另外一个乘数一定小于等于值小的值，因此面积一定减小，而我们要求最大的面积，因此值大的指针不动，而值小的指针向内移动遍历
代码语言：javascript复制双指针 第一次不看题解有思路 看来多刷题真的很有用
class Solution {
public int maxArea(int[] height) {
if(height.length<2) return 0;
int left = 0;
int right = height.length-1;
// ans 为结果 min为两个木板的长度最小值
int ans = 0; int min = 0;
while(left<right){
min = Math.min(height[left],height[right]);
ans = Math.max(ans,(right-left)*min);
// 如果左边短 就右移
if(height[left]<height[right]){
left ;
}else{
// 右边短就左移
right --;
}
}
return ans;
}class Solution {
public:
int maxArea(vector<int>& height) {
//定义双指针
int left=0;
int right=height.size()-1;
int ans=-99999;
while(left<right){
int area=min(height[left],height[right])*(right-left);
ans=max(ans,area);
if(height[left]<height[right])left ;
else{
right--;
}
}
return ans;
}
};
