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),只需要额外的常数级别的空间