Leetcode 11 盛最多水的容器

题目链接：11. 盛最多水的容器

解答

对任意$(i,j)$组合，面积$area=min(height[i],height[j])*(j-i)$

方法一：暴力搜索

遍历所有$(i,j)$，代码：

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

时间复杂度：$O(N^2)$，空间复杂度：$O(1)$

方法二：双指针

1. 定义左右指针$i$和$j$，分别代表容器的左右边界。

2. 指定两个指针移动状态：

   1. 原则：

      • 两个指针只会向内收缩，即$i$只能增大，$j$只能减小
      • 指针的移动朝着area可能增大的方向移动

   2. 移动方法：取二者高度较小的向内收缩。

      1. 原因：
         • 高度较大的向内收缩，$area$只会不变或者减小，因为$min(height[i],height[j])$要么不变，要么减小，并且$(j-i)$变小了。
         • 高度较小的向内收缩，$area$可能会变大，因为$min(height[i],height[j])$可能会变大，尽管$(j-i)$变小，但综合$area$存在变大的可能性。（这里说可能变大，也存在变小的可能，就是高度较小的，它更小了）
      2. 相比于暴力搜索忽略的$(i,j)$的状态都是比$area$小的，不必重复计算

   3. 代码：

      class Solution {
          public int maxArea(int[] height) {
              int i=0,j=height.length-1,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;
          }
      }

      时间复杂度：$O(N)$，空间复杂度：$O(1)$