2019-08-12【LeekCode题库problem-11】

CoffeeRabbit · · 96 次点击 · · 开始浏览    

GitHub 地址:coffeeTu-code

LeekCode 地址:题库

Language:Golang

/*

@题目

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

question_11.jpg

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水的最大值为 49(high=7,wide=9-2,area=high*wide)。

@示例:

输入: [1,8,6,2,5,4,8,3,7]

输出: 49

@题目大意

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

@解题思路

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

*/

func maxArea(height []int) int {
    var (
        width,
        high 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--
        }

        if width*high > max {
            max = width * high
        }
    }
    return max
}

本文来自:简书

感谢作者:CoffeeRabbit

查看原文:2019-08-12【LeekCode题库problem-11】

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

96 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传