leetcode11.盛最多水的容器

题目链接

解法一：暴力求解

对于本题，最简单，暴力的方法就是循环嵌套，暴力求解。对于每一个柱子，都算出以这个柱子为左边界形成的容器面积，依次比较，求出盛水最多的容器。

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        for(int i = 0;i < height.length;i++){
            for(int j = i + 1;j < height.length;j++){
                maxArea = maxArea < getArea(height,i,j) ? getArea(height,i,j) : maxArea; 
            }
        }
        return maxArea;
    }

    private int getArea(int[] height,int i,int j){
        return Math.min(height[i],height[j]) * (j - i);
    }
}

解法一的时间复杂度为O(n ^ 2),提交代码运行的时间也不理想。

解法二：夹逼思想

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        for(int i = 0,j = height.length - 1;i < j;){
            int minHeight = height[i] < height[j] ? height[i++] : height[j--];
            // 注意注意，i或者j已经执行完+1或者-1的操作了
            // maxArea的计算公式变为了minHeight * (j - i + 1)
            maxArea = Math.max(minHeight * (j - i + 1),maxArea);
        }
        return maxArea;
    }
}

解法二的思想是夹逼，或者说是双指针也可以。设置双指针i和j分别位于容器壁的两端，比较arr[i]与arr[j]的高度，如果arr[i]小于arr[j]，则i指针向右移动；如果arr[j]小于arr[i],则j指针向左移动。直到i == j的时候，返回结果。所以在时间复杂度上来讲是O(n)。具体的思路，可以看代码，理清思路是比较简单的，但是夹逼的证明比较繁琐，可以看这篇文章 双指针法正确性证明