LeetCode每日一题：盛水最多的容器

示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49

1.首先先介绍暴力解法，也就是最容易想出来的方法

大体思路就是遍历，把所有结果都遍历一遍然后相比较，最后返回最大的那个

    public int maxArea(int[] height) {             
        int res = 0;        
        for(int i = 0;i < height.length;i++){   
          for(int j = i;j < height.length;j++){ 
            if(res < Math.min(height[i], height[j]) * (j - i)) {
                res = Math.min(height[i], height[j]) * (j - i);             
            }               
         }
        }
        return res;
  }

虽然简单但是时间复杂度还不是最优

时间复杂度：O(N!)

2.第二种方法就是双指针，这也是目前的官方给出的最优方法

算法流程：设置双指针 left,right分别位于容器壁两端，根据规则移动指针，并且更新面积最大值 res，直到 left == right 时返回 res。
指针移动规则与证明：每次选定围成水槽两板高度 height[left],height[jright] 中的短板，向中间收窄 1 格。以下证明：
- 设每一状态下水槽面积为 S(left, right),(0 <= left < right < height.length)，由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(left, right) = min(height[left], height[right]) × (right - left)。
- 在每一个状态下，无论长板或短板收窄 1 格，都会导致水槽底边宽度 −1：
  - 若向内移动短板，水槽的短板 min(height[left], height[right])可能变大，因此水槽面积 S(left, right) 可能增大。
  - 若向内移动长板，水槽的短板 min(height[left], height[right])不变或变小，下个水槽的面积一定小于当前水槽面积。

代码实现

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

}

时间复杂度：O(N),双指针总计最多遍历整个数组一次
空间复杂度：O(N),只需要额外的常数级别的空间