11. Container With Most Water

Leetcode 链接

题目

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

题意解析

给出 n 个正整数 a1, a2, ..., an, 每个数代表坐标 (i, ai). 任意两个点向 x 轴引垂直线后可以与 x 轴形成一个能装水的容器。求该容器的最大容量。

解决方案

• 定义两个下标： left, right 分别从数组的起始位置和末尾位置开始向中间遍历靠拢
• 容器的面积定义为： min(height[left], height[right]) * (right - left)
• 当左右两边下标向中间靠拢时，横坐标上的距离是变小的，要使整体面积变大就需要坐标点的纵坐标值变大

Go 代码

func min(a, b int) int {
    if a < b {
        return a
    } 
    return b
}

func max(a, b int) int{
    if a > b {
        return a
    }
    return b
}

func maxArea(height []int) int {
    left := 0
    right := len(height) - 1

    res := -1

    for left < right {
        h := min(height[left], height[right])
        res = max(res, h * (right-left))

        for (left < right) && (height[left] <= h) {
            left ++
        }

        for (left < right) && (height[right] <= h){
            right --
        }
    }

    return res
}