leetcode第11题：盛最多水的容器

二次循环

这道题比较容易想到的就是通过二次循环遍历所有能盛的水的体积。

代码

class Solution {public int maxArea(int[] height) {// 记录最大体积int max = 0;// 左侧for(int i=0;i<height.length;i++){// 右侧for(int j =i+1;j<height.length;j++){// 计算体积int volumn = (j-i)*Math.min(height[i],height[j]);// 比较体积与当前最大值if(volumn>max)max = volumn;}    }return max;}
}

但是很明显，当前这种方案的时间复杂度为O(n*n)，会在提交时超出时间限制。

双指针优化

解析

那么尝试进行优化，寻找这种情形下有没有什么特点可以被发现。

这里可以观察体积计算的公式
v = height*width，
(其中width=right-left; height=min(heights[right],heights[left]))的特性。

假设我们通过双指针从height数组左右两侧依次向中间夹，那么width就会一直减小。而此时，我们只有让水桶的木板变高才会让容器的体积增大（一个变量始终减小或者增大，只需要考虑另一个变量就可以）。
因此在移动过程中，如果移动较高的那么体积必然减小，只有移动较低的才会可能让体积增大（决定木桶体积的是最短板，而不是最长板）。
我们在遍历的过程中不断移动较短的部分，即：

if(height[left]>height[right]){right--;
}else{left++;
}

同时不断计算当前移动后是不是大于记录的最大容量，如果大于那么更新最大容量。

int volumn = Math.min(height[right],height[left])*(right-left);
if(volumn>max)max = volumn;

因此本道题目关键：

1.决定木桶体积的是最短板，而不是最长板
2.两个变量计算的时候，如果控制其中一个始终减小或者增加，那么只需要关注另一个变量就可以
3.如果两个变量增加减小无法控制，那么时间复杂度只能提高。

代码

class Solution {public int maxArea(int[] height) {if(height.length==1)return 0;int left = 0;int right = height.length-1;int max = Math.min(height[left],height[right])*(right-left);// 左右依次遍历// 移动较小的那根while(left<right){if(height[left]>height[right]){right--;}else{left++;}int volumn = Math.min(height[right],height[left])*(right-left);if(volumn>max)max = volumn;}return max;}
}