算法练习8：计算最大盛水容器(leecode 11)

题目：
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

其实本质上是求一个长方形的最大面积，看什么x,y轴在什么情况下能得到最大面积的长方形；

暴力解法

通过两层遍历，计算所有的长方形面积值，然后得出最大值

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

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

双指针法

做法：
初始时[1,8,6,8,3,7]

1. 一个指针left指向最数组最前边下标left = 0， 一个指针right指向数组尾下标right = height.length -1 = 5，此时横坐标的长度8是最长的情况，此时纵坐标只会取决于两指标的纵坐标中最小值；计算这时候的面积值:
   area = right * min(height[left], height[right]) = 5 * min(1, 7) = 5，这个值就是横坐标最大时的最大面积；

2. 此时，当横坐标递减1变小一格为4时，此时的最大面积是多少？显然，只有要么左边移一格，或者右边移一格两种选择，这仍然取决于最小纵坐标是多少，那么肯定是纵坐标越大，那么它的面积就越大。所以纵坐标大的指针我们保持不变，我们会移动纵坐标较小的那个指针，left右移1位，left = 1，面积变为：
   area = (right - left) * min(height[left], height[right]) = (5-1) * min(8, 7) = 28
   这就是横坐标为7时，最大面积；为了验证这个结论，我们可以反向验证下移动右指针(right-1)的话的结果：
   area = (right - left) * min(height[left], height[right]) = (7-0) * min(1, 3) = 7 < 28

3. 继续，当横坐标变为3格时， right指针的值7 < left指针的值8，所以移动右指针向左一格指向right = 4，指向数值3:
   area = (4-1) * min(8, 3) = 9

4. 继续，height[right] = 3, height[left] = 8, 所以移动右指针向左一格right = 3，指向数值8:
   area = (3-1) * min(8, 8) = 16

5. 继续，height[right] = 8, height[left] = 8, 两值相等，我们可以任意移动哪个指针都行，比如我移动左指针 left +1 = 2, 指向数值6:
   area = (3-2) * min(6, 8) = 8

6. 继续，height[right] = 8, height[left] = 6, 我们移动左指针left +1 = 3, 此时左指针和右指针重合了，是横坐标为0格，无法计算面积，此时，结束遍历

7. 对比这一轮里所求的所有面积，最大的面积就是我们所求的最大盛水容器了，即28

• 时间复杂度： O(n)
• 空间复杂度：常量,O(1)

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  let left = 0;
  let right = height.length -1;
  let maxArea = right * Math.min(height[left], height[right])
  let area = 0;
  while(left !== right) {
    if(height[left] < height[right]) {
      left++;
    }else {
      right--;
    }
    area = (right - left) * Math.min(height[left], height[right])
    if(area > maxArea) {
      maxArea = area
    }
  }
  return maxArea
};

console.log(maxArea([1,8,6,8,3,7])) // 28