11. Container With Most Water]

题目

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.

给定n个非负整数a1, a2,…,an,其中每个代表坐标(i, ai)上的一点。画n条垂直线,使直线i的两个端点分别为(i, ai)和(i, 0)。找出两条直线,它们与x轴一起构成一个容器,使容器中包含的水最多。

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

你不能倾斜容器,并且n至少是2。

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

以上垂直线用数组[1,8,6,2,5,4,8,3,7]表示。在这种情况下,容器可以容纳的最大水域面积(蓝色部分)是49。

栗子1:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

题目大意

给出一个非负整数数组 a1,a2,a3,…… an,每个整数标识一个竖立在坐标轴 x 位置的一堵高度为 ai 的墙,选择两堵墙,和 x 轴构成的容器可以容纳最多的水。

解题思路

这一题也是对撞指针的思路。首尾分别 2 个指针,每次移动以后都分别判断长宽的乘积是否最大。

代码


func maxArea(height []int) int {
    max, start, end := 0, 0, len(height)-1
    for start < end {
        width := end - start
        high := 0
        if height[start] < height[end] {
            high = height[start]
            start++
        } else {
            high = height[end]
            end--
        }

        temp := width * high
        if temp > max {
            max = temp
        }
    }
    return max
}
最后修改:2021 年 07 月 29 日 09 : 41 AM
如果觉得我的文章对你有用,请随意赞赏