NOTES · 学习笔记

盛最多水的容器:移动矮的那一端

LeetCode双指针 · 中等约 4 分钟

题目

我们先看思路。这道题要我们找到两条垂线组成的最大面积,可以用双指针——双指针存的就是我们寻找的那两条垂线的位置。

如何寻找最大面积?看示例:数组 [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
}