Date：2019-4-13

题目地址：https://leetcode-cn.com/problems/container-with-most-water/

给定 n 个非负整数 a，a…，a每个数代表坐标中的一个点 (i, a) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
盛最多水的容器 - 图1
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7] 输出: 49

官方解法：

如题意，垂直的两条线段将会与坐标轴构成一个矩形区域，较短线段的长度将会作为矩形区域的宽度，两线间距将会作为矩形区域的长度，而我们必须最大化该矩形区域的面积。

方法一：暴力法

算法
在这种情况下，我们将简单地考虑每对可能出现的线段组合并找出这些情况之下的最大面积。

  1. public class Solution {
  2.   public int maxArea(int[] height) {
  3.     int maxarea = 0;
  4.     for (int i = 0; i < height.length; i++)
  5.       for (int j = i + 1; j < height.length; j++)
  6.         maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
  7.     return maxarea;
  8.   }
  9. }

复杂度分析

  • 时间复杂度：O(n^2)O(n_2)，计算所有 \ frac{n(n-1)}{2}2_n(n−1) 种高度组合的面积。
  • 空间复杂度：O(1)O(1)，使用恒定的额外空间。

方法二：双指针法

算法
这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。
我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxareamaxarea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxareamaxarea，并将指向较短线段的指针向较长线段那端移动一步。
查看下面的例子将有助于你更好地理解该算法：

  1. public class Solution {
  2.   public int maxArea(int[] height) {
  3.     int maxarea = 0, l = 0, r = height.length - 1;
  4.     while (l < r) {
  5.       maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
  6.       if (height[l] < height[r])
  7.         l++;
  8.       else
  9.         r--;
  10.     }
  11.     return maxarea;
  12.   }
  13. }

这种方法如何工作？
最初我们考虑由最外围两条线段构成的区域。现在，为了使面积最大化，我们需要考虑更长的两条线段之间的区域。如果我们试图将指向较长线段的指针向内侧移动，矩形区域的面积将受限于较短的线段而不会获得任何增加。但是，在同样的条件下，移动指向较短线段的指针尽管造成了矩形宽度的减小，但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段，这可以克服由宽度减小而引起的面积减小。
点击这里查看进一步说明，点击这里查看相关证明。

复杂度分析

  • 时间复杂度：O(n)O(n)，一次扫描。
  • 空间复杂度：O(1)O(1)，使用恒定的空间

我的理解和解法

方法一： 暴力法

图解
image.png

const maxArea = (arr) => {
    let max = 0
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            max = Math.max(
        max,
        Math.min(arr[i], arr[j]) * (j - i) //计算每个的面积去和 max 进行比较
      )
        }
    }
    return max
}

方法二： 双指针法

图解：
在下面的图中，x表示我们不需要计算这种情况下的体积:(1)在对角线上，两条线重叠;(2)矩阵左下三角区域与右上区域对称。

我们从(1,6)处的体积开始计算，用o表示。现在，如果左边的线比右边的线短，那么第一行(1,6)处的所有元素的体积都更小，所以我们不需要计算那些情况(交叉了——)
1 2 3 4 5 6
1 x ———- o
2 x x
3 x x x
4 x x x x
5 x x x x x
6 x x x x x x

接下来我们移动左边的线并计算(2,6)现在，如果右边的线更短，下面(2,6)的所有情况都被排除
1 2 3 4 5 6
1 x ———- o
2 x x o
3 x x x |
4 x x x x |
5 x x x x x |
6 x x x x x x

无论这条o路径如何变化，我们最终只需要找到这条路径上的最大值，一共包含n-1种情况。
1 2 3 4 5 6
1 x ———- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

const maxArea = (arr) => {
  let max = 0
  let i = 0
  let j = arr.length -1
  while(j > i) {
    max = Math.max(
      (j-i) * Math.min(arr[i], arr[j]),
      max
    )
    arr[i] > arr[j]? j--: i++
  }
  return max
}

为什么要做这道题，它的实际运用场景是什么

当我们遇到那些需要进行计算某一个区间内的统计数据信息的时候，我们会用到这种算法