11.盛最多水的容器

盛最多水的容器

给定一个长度为 n 的整数数组  height 。有  n  条垂线，第 i 条线的两个端点是  (i, 0)  和  (i, height[i]) 。

找出其中的两条线，使得它们与  x  轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为  49。

示例 2：

输入：height = [1,1]
输出：1

提示

• n == height.length
• 2 <= n <= $10^5$
• 0 <= height[i] <= $10^4$

解析

方法 1: 假如用双层循环，时间复杂度为 $O(n^2)$

var maxArea = function (nums, target) {
  let area = 0;

  for (let i = 0; i < height.length - 1; i++) {
    for (let j = i + 1; j < height.length; j++) {
      area = Math.max(area, (j - i) * Math.min(height[i], height[j]));
    }
  }
  return area;
};

由于时间复杂度太高，很可能导致提交超限，我们考虑用双指针来解决该问题

方法 2:

开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。

var maxArea = function (height) {
  let area = 0;
  let left = 0;
  let right = height.length - 1;

  while (left < right) {
    area = Math.max(
      area,
      (right - left) * Math.min(height[left], height[right])
    );
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return area;
};