NOTES · 学习笔记
盛最多水的容器:移动矮的那一端
题目
我们先看思路。这道题要我们找到两条垂线组成的最大面积,可以用双指针——双指针存的就是我们寻找的那两条垂线的位置。
如何寻找最大面积?看示例:数组 [1,8,6,2,5,4,8,3,7] 表示九条垂线的高度。高度应该是我们要找的那两条垂线中较矮那一条的高度,用 min(height[left], height[right]) 保存起来。宽度呢?第一个指针 left 保存最左边垂线的位置,第二个指针 right 保存最右边垂线的位置,宽度就是最右边的位置减去最左边的位置,面积就算出来了。
如何判断是最大面积?假设 left 在最左边,right 在最右边:此时高度取最小值 1,宽度 right-left=8-0,area=1×8=8,很明显不是最大面积——因为左边太矮了。那我们将 left 右移,left 来到第二条垂线的位置。此时高度取最小值 7,宽度 right-left=8-1=7,area=7×7=49,是最大面积。
所以可以得出:想找到最大面积,就是将矮的那一条垂线移动。left 矮就右移 left++;right 矮就左移 right--。
func maxArea(height []int) int {
left := 0 // 定义指针,表示最左边的垂线位置
right := len(height)-1 // 定义指针,表示最右边垂线的位置
result := 0 // 我们最后输出这个结果
area := 0 // 得到的面积
for left < right { // 当左边<右边时,我们开始遍历求面积
h := min(height[left], height[right]) // 求高度,两根垂线组成的高度是矮的那一方
width := right-left // 求宽度,宽度就是用右边垂线的位置减去左边垂线的位置
area = h * width // 求面积
result = max(result, area) // 我们将目前最大面积保存在result中
if height[left] < height[right] {
left++ // 左边较矮,移动左指针,寻找更高的柱子
} else {
right-- // 右边较矮,移动右指针,寻找更高的柱子
}
}
return result
}