1.题目描述
给定 n 个非负整数 
，
，...，
，每个数代表坐标中的一个点 (i, 
) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ) 和 (i, 0)。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
2.提交记录
11.暴力枚举法.png
11.双指针法.png
3.算法思想
这道题目的意思是在输入的int *height中，找到两个数字使得他们在坐标轴上围成的面积最大。
方法一：暴力枚举法。
使用两层循环，对每种可能进行暴力枚举。但是这种方法使得时间复杂度较高，速度较慢。
方法二：双指针法。
为了降低时间复杂度，我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾，即定义两个整型指针 left 和 right ，使得left = 0；right = heightSize - 1。
由题意得，面积的初始值为*(height + left) * (right -left)。为了确保面积最大，我们会找出两个指针所指向的两条线段形成的区域，持续更新最大面积，每次 *(height + left) 和 *(height + right) 值较小的一方，都要往数组中间移动一步。
4.实现过程
int maxArea(int* height, int heightSize){
int max = 0,temp = 0;
for(int i = 0;i < heightSize-1;i++){
for(int j = i+1;j < heightSize;j++){
if(*(height+i) < *(height+j)){
temp = (*(height+i) * (j-i)) ;
}else{
temp = (*(height+j) * (j-i)) ;
}
if(max < temp){ max = temp; }
}
}
return max;
}
int maxArea(int* height, int heightSize){
int left = 0 , right = heightSize - 1;
int max = 0,temp = 0;
while(left < right){
if( *(height + left) < *(height + right) ){
temp = *(height + left) * (right - left) ;
left++;
}else{
temp = *(height + right) * (right - left) ;
right--;
}
if(max < temp){ max = temp; }
}
return max;
}
5.复杂度分析
- 时间复杂度：O(n2)；
- 空间复杂度：O(1)；
- 时间复杂度：O(n)；
- 空间复杂度：O(1)；
