[11]盛最多水的容器

题目：https://leetcode-cn.com/problems/container-with-most-water/
方法一：暴力解法，时间复杂度 O(N2)

 public int maxArea(int[] height) {        
        int maxS = 0;
        int tmpS = 0;
        for (int i = 0; i < height.length ; i++) {
            for (int j = i+1; j < height.length; j++) {
                if(height[i]<= height[j]){
                    tmpS = height[i]*(j-i);
                }else{
                    tmpS = height[j]*(j-i);
                }
                if(tmpS > maxS){
                    maxS = tmpS;
                }
            }
        }
        return maxS;
 }

方法二 :

思路：面积 : 两个柱子之间的距离d*两个柱子较小值min
1、首先取最左和最右两个柱子，
距离d=9-1 = 8
较小值：min = 3
面积 8x3 = 24
2、如果最左边柱子不动(h=3)，无论移动右边哪根柱子，都不可能比最右边的柱子距离更大，
所以移动右边会让距离变小，因为最左边的柱子不动，所以水位最大值为3，整体来看，移动高的柱子会让面积变小
3、如果最右边柱子不动，无论移动左边的哪根柱子，距离都会变小，但水位会变不确定，水位最大值为7，整体来看，移动矮的柱子面积变小变大不确定
4、综上述，应该移动小的柱子

时间复杂度o(n)

public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int maxS = 0;
        while (left<right){
            maxS = Math.max(maxS,Math.min(height[left],height[right])*(right-left));
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
        }
        return maxS;
    }