LeetCode算法(和中等打的有来有回)——盛最多水的容器

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;
    }
}