盛最多的水的容器

盛最多水的容器

难度：中等
问题描述：
给你 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。

链接：原题链接

解法

解法1：穷举法

• 思路：略
• 代码：

  // 穷举法
  func maxArea(height []int)  int {
  	length := len(height)
  	maxAreas := 0
  	for indexX, heightX := range height {
  		for indexY := indexX + 1; indexY < length; indexY++ {
  			duration := indexY - indexX
  			minHeight := heightX
  			if height[indexY] <= heightX {
  				minHeight = height[indexY]
  			}
  			if maxAreas <  minHeight * duration {
  				maxAreas = minHeight * duration
  			}
  		}
  	}
  	return maxAreas
  }

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

解法2：双指针法

• 思路：容量大就意味着要不长度够宽，要不高度够高。那么最宽的就是整个输入的收尾长度。由于中间的宽度小于两边的宽度，所以只有比两边更高的高度才有可能有更大的面积。所以，使用双指针从当前元素位置和末尾的两端往中间靠拢，不断寻找更高的边，这样只需要 O(N) 即可完成遍历.
• 代码：

  func maxAreaWithTwoPoint(height []int)  int {
  	length := len(height)
  	pointA, pointB := 0, length - 1
  	maxAreas := 0
  
  
  	for areas :=0 ; pointA < pointB; {
  		if height[pointA] <= height[pointB] {
  			areas = height[pointA] * (pointB - pointA)
  			if maxAreas < areas {
  				maxAreas = areas
  			}
  			pointA++
  		}
  
  		if height[pointA] > height[pointB] {
  			areas = height[pointB] * (pointB - pointA)
  			if maxAreas < areas {
  				maxAreas = areas
  			}
  			pointB--
  		}
  	}
  
  	return maxAreas
  }

  时间复杂度：O(N)
  空间复杂度：O(1)