LeetCode 11. 盛最多水的容器(双指针)
发布日期:2021-07-01 03:14:01
浏览次数:2
分类:技术文章
本文共 1296 字,大约阅读时间需要 4 分钟。
文章目录
1. 题目信息
给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。说明:你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例:输入: [1,8,6,2,5,4,8,3,7]输出: 49
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:
- 两个指针 i, j 分别指向首尾,水的面积 s = ( j − i ) ∗ m i n ( h i , h j ) s = \left ( j-i \right )*min(hi,hj) s=(j−i)∗min(hi,hj)
- 如果哪边的 h 小,那边的指针向中间移动
class Solution { public: int maxArea(vector & height) { int i = 0, j = height.size()-1, s, maxS = 0; while(i < j) { if(height[i] > height[j]) { s = (j-i)*height[j]; --j; } else { s = (j-i)*height[i]; ++i; } if(s > maxS) maxS = s; } return maxS; }};
class Solution { //2020.4.18public: int maxArea(vector & height) { int i = 0, j = height.size()-1, area = 0; while(i < j) { area = max(area, (j-i)*min(height[i],height[j])); if(height[i] <= height[j]) i++; else j--; } return area; }};
转载地址:https://michael.blog.csdn.net/article/details/100545403 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月14日 06时26分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
java常用类 String面试题
2019-04-30
四线触摸屏原理
2019-04-30
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
java.net.BindException: 无法指定被请求的地址
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01