栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 系统运维 > 运维 > Linux

盛最多水的容器

Linux 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

盛最多水的容器

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

解题方式:双指针法

解题思路:如下

通过题目中的描述可以得出以下这两个结论

一、两个木板的盛水量和短的那根正相关,和长的那根无关。

二、两个木板的盛水量和它们之间的距离正相关。

既然知道两个木板的盛水量和它们之间的距离正相关,那就直接取最大正相关值,从x轴的两端开始,然后通过某种策略移动两端的指针。

指针移动的策略:由于盛水量和短的那根正相关和长的那根无关,因此在移动指针时应该向内移动短的那根以寻求更多盛水的可能性(如果向内移动长的那根只会让盛水量变小,没有变大的可能)。每次移动指针计算当前盛水量比较上一次的盛水量,保存大的用于下次比较。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/461181.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号