前端刷题路-Day53：盛最多水的容器（题号11）-一一网

这是我参与更文挑战的第17天，活动详情查看：更文挑战

盛最多水的容器（题号11）

题目

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 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
复制代码

示例 3：

输入：height = [4,3,2,1,4]
输出：16
复制代码

示例 4：

输入：height = [1,2,1]
输出：2
复制代码

提示：

n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

链接

leetcode-cn.com/problems/co…

解释

这题啊，这题是十分愚蠢。

讲真，这题应该算是一道经典双指针问题，而一开始，我的确也想到了双指针，可惜脑子没转过弯来，一直卡死在要考虑所有可能性的上面无法自拔，然后尝试了三种双循环，结果是显然的，3次都GG了，而且是挂在同一个用例上。

双指针的解法其实非常简单，首先从把左右指针放到数组首尾，之后开始向内缩减，那什么时候移动左指针，什么时候右指针？

其实非常简单。

假设现在左指针比右指针的数小，有两种移动办法：

移动左指针

那么此时的左指针有可能更大，有可能更小，这个问题是不重要的。

重要的是距离。

此时距离减少了1，两个指针间最小值会变化，可能会更大，也有可能会更小
移动右指针

此时距离依旧减少了1，两个指针的最小值只会变小，不会变大，这问题就出现了

也就是说，不管移动左指针还是右指针，距离其实都会减去1，如果我们选择移动较大的那个数，那么两数的最小值只会更小不会更大，而移动较小的那个数，可能会更大，也可能会更小。

那么为了这更大的可能，我们只能移动较小的那个数，暨此才能得到可能的最大值。

有些时候就是这一点点简单的东西没有想明白，导致解答不出来，也是没有办法。

自己的答案（暴力 -> 双循环）

var maxArea = function(height) {
  var len = height.length
      max = 0 
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      max = Math.max(Math.min(height[i], height[j]) * (j - i), max)      
    } 
  }
  return max
};
复制代码

经典双循环暴力解法，考虑每一种可能性，在55/60个用例时GG。

自己的答案（暴力 -> 数组缓存）

 var maxArea = function(height) {
  var len = height.length
      max = 0
      arr = new Array(len).fill(0)
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      arr[j - i] = Math.max(arr[j - i], Math.min(height[i], height[j]))
    } 
  }
  for (let i = 1; i < arr.length; i++) {
    max = Math.max(max, arr[i] * (i))    
  }
  return max
};
复制代码

该方法利用数组作为缓存，存储的结果是每种距离中的最小数们的最大值，减少了上一种方法中每次遇到新的情况都需要乘一次的情况。

结果毫无意义，依旧在55/60个用例时GG。

自己的答案（暴力 -> 滑动窗口）

 var maxArea = function(height) {
  var len = height.length
      max = 0
  for (let i = 1; i < len; i++) {
    var left = 0
        right = left + i
        maxHeight = 0
    while (right < len) {
      maxHeight = Math.max(maxHeight, Math.min(height[left], height[right]))
      ++left
      ++right
    }
    max = Math.max(maxHeight * i, max)
  }
  return max
};
复制代码

在外层循环时，考虑所有窗口长度的可能性，之后开始滑动窗口，一直滑动到最右侧为止，在滑动过程中记录最小数们的最大值，滑动完一种长度后和max进行一次比较，其实和上一种方法查不多，只是额外空间从数组变成了一个变量。

结果自然也是一样的，在55/60个用例时GG。

更好的方法（双指针）

OK，终于来到经典双指针解法了，代码非常简单?：

var maxArea = function(height) {
  var left = 0
      right = height.length - 1
      max = 0
  while (left < right) {
    max = Math.max(Math.min(height[left], height[right]) * (right - left), max)
    if (height[left] < height[right]) {
      ++left
    } else {
      --right
    }
  }
  return max
};
复制代码

和解释里说的一样，判断两个指针代表的数字大小，移动小的那一个，每移动一次就和max比较一次，挪动完成即可得到最终结果。

还是棋差一招啊，毫无办法。

复杂度分析