LeetCode 11 盛最多水的容器

题目:

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

解题:

循环求最大值,大力出奇迹

代码:


func maxArea(height []int) int {
    max, l := 0, len(height)
    min := func(x, y int) int {
        if x > y {
            return y
        }
        return x
    }
    for i := 0; i < l; i++ {
        for j := i + 1; j < l; j++ {
            tmp := (j - i) * min(height[i], height[j])
            if tmp > max {
                max = tmp
            }
        }
    }
    return max
}

官方给了个很长很变态的数组,测试超时了,我觉得代码是对的,消耗估计太多了

官方解答

func maxArea(height []int) int {
    i, r := 0, len(height)-1
    min := func(x, y int) int {
        if x > y {
            return y
        }
        return x
    }
    max := func(x, y int) int {
        if x > y {
            return x
        }
        return y
    }
    area := 0
    res := 0
    for i < r {
        area = min(height[i], height[r]) * (r - i)
        res = max(res, area)
        if height[i] < height[r] {
            i++
        } else {
            r--
        }
    }
    return res
}

双指针,只循环一次,牛逼

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注