Lever's Castle
11. 盛最多水的容器
December 04, 2019
https://leetcode-cn.com/problems/container-with-most-water/
使用语言：Go
解法一：
func maxArea(height []int) int {
var max int
for i := range height {
area := _maxArea(height[i:])
if area > max {
max = area
}
}
return max
}
func _maxArea(height []int) (max int) {
if len(height) <= 1 {
return
}
startH := height[0]
for i, h := range height {
var area int
if h < startH {
area = i * h
} else {
area = i * startH
}
if area > max {
max = area
}
}
return
}这种解法很容易理解。我们只要把问题分解成每一段的最大面积是多少，然后汇总起来求最大的面积。
解法二：
func maxArea(height []int) int {
i := 0
j := len(height) - 1
var max int
for i < j {
var area int
if height[i] > height[j] {
area = (j - i) * height[j]
j--
} else {
area = (j - i) * height[i]
i++
}
if area > max {
max = area
}
}
return max
}这个解法需要深入思考下才能想到。我们先按照题目需求列个表达式出来：
area = width * height那要求最大面积，就要找到宽和高的最佳组合。
height[0] 到 height[len(height) - 1] 是宽度最大的时候，此后当我们逐渐向后遍历时，宽度肯定是在逐渐减小的，因此我们要保证高度是在逐渐增大的，才有可能得到的面积比 (height[0], height[len(height) - 1]) 的大。
因此，我们用 i 和 j 分别控制容器的顶和底。i 不断向后递增，j 则不断向前递减。当 height[i] > height[j] 时，i 不动，递减 j（因为 i 对应的 height 更大，而我们希望 height 是不断增大的，这样才有可能比当前的最大面积还大）。同理，height[i] < height[j] 时，j 不动，i 递增。
最终，得到了上述代码。
痕迹
没有过去，就没法认定现在的自己