LeetCode - 盛最多水的容器

LeetCode第11题，难度中等，严重怀疑该题在英文版里是不是第11题，一点印象都没有.

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

题目描述：

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

说明：你不能倾斜容器，且 n 的值至少为 2。

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/container-with-most-water

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

看到这题，第一反应就是，一个个坐标遍历过去，分别算出最大的容积，然后取最大值。这个就是暴力解法。

我的解法是，遍历所有的可能性，然后分别求出当前的高度，并计算容积，最后取最大值。

很明显暴力解法是很慢的，因为有很多无用的循环比较在其中。更快的方法也有，就是双指针法。

双指针法的思路就是在头尾各放置一个指针，然后获取当前的容积。然后怎么移动指针呢？将高度更小的指针往中心移动，也就是左指针向右，右指针向左。为什么这么做？是因为高度和长度是制约容积的两大因素，如果容积受限于高度，就应该想办法去获取更高的高度，虽然长度可能会有损失。

双指针法的话，只需要遍历一遍数组就好了，很明显更高效。

中文官网题解：

https://leetcode-cn.com/problems/container-with-most-water/solution/

个人题解：

func maxArea(height []int) int {
  max := 0
  for i := 0; i < len(height); i++ {
    for j := i + 1; j < len(height); j++ {
      var h int
      if height[i] >= height[j] {
        h = height[j]
      } else {
        h = height[i]
      }
      if h*(j-i) > max {
        max = h * (j - i)
      }
    }
  }
  return max
}

结果：

没想到运行了1000多毫秒之后，我仍然不是垫底的，但是距离前面太远了.