5.盛最多水的容器

题目概述：给定一些柱子的高度，规定两根柱子之间所能围成的面积(以两者中较短的一根的高度作为矩形的高)。问这些柱子中所能围成的最大面积
解题思路1：很明显，水量=(j - i) * min(height[i],height[j]);
当j从后往前枚举有一个特性：当height[j] >= height[i]时就可以不用再枚举了，因为
此时min(height[i],height[j])已经达到了最大：height[i],如果继续枚举j-i减小
显然不是答案
时间复杂度:\(O(n^2)\),但由于我们有一个优化，以及leetcode数据没有设置边界数据，ac了
代码：

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        //水量=(j - i) * min(height[i],height[j]);
        //j从后往前枚举有一个特性：当height[j] >= height[i]时就可以不用再枚举了，因为
        //此时min(height[i],height[j])已经达到了最大：height[i],如果继续枚举j-i减小
        //显然不是答案
        int res = 0;
        for(int i = 0; i < n; i ++){
            int ma = 0;
            for(int j = n - 1; j > i; j --){
                ma = Math.max(ma,(j - i) * Math.min(height[i],height[j]));
                if(height[j] >= height[i])break;
            }

            res = Math.max(res,ma);
        }
        return res;
    }
}

解题思路2：对上述代码继续进行优化。上述代码存在的缺陷在于，当j所指向的柱子高度不小于i所指向的柱子高度时，j又置为n-1.这时所得到的答案就是i这根柱子所能围成的最大面积。我们可以进一步思考：是不是可以采用同样的方法来得到j这根柱子所能围成的最大面积呢？采用同样的思路，我们移动i指针，当其高度不小于j指针的高度时，所得到的答案就是j柱子所能围成的最大面积

时间复杂度：\(O(n)\)
代码：

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int i = 0,j = n - 1;
        int res = 0;
        while(i < j){
            int area = Math.min(height[i],height[j]) * (j - i);
            res = Math.max(res,area);
            if(height[i] <= height[j])i++;
            else j--;
        }

        return res;
    }
}