LeetCode(11)题解: Container With Most Water
2024-09-08 08:09:44
https://leetcode.com/problems/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.
Note: You may not slant the container.
思路:
考虑从边界向里缩减范围。最重要的是注意到,假设现在边界的height是a和b,那么想在内部有别的点能比a、b框成的体积大,那么这个点一定得比a、b中的最小者大。所以不断从边界height较小的点向内缩减,直到内部为空。
只需遍历数组一次,所以复杂度为O(n)。
AC代码:
class Solution {
public:
int maxArea(vector<int>& height) {
int i,j,n=height.size(),a=,b=n-,contain=min(height[],height[n-])*(n-);
while(a<b){
if(height[a]<height[b]){
for(i=a;i<b;i++){
if(height[i]>height[a])
break;
}
if(min(height[i],height[b])*(b-i)>contain){
contain=min(height[i],height[b])*(b-i);
}
a=i;
}
else{
for(j=b;j>a;j--){
if(height[j]>height[b])
break;
}
if(min(height[j],height[a])*(j-a)>contain){
contain=min(height[j],height[a])*(j-a);
}
b=j;
}
}
return contain;
}
};
最新文章
- TFS工作区(Workspaces )命令
- Opera浏览器导出收藏到Chrome,和几个Chrome的一些小技巧
- 上海敏行医学招聘物理仿真,3D图形人才
- SOC芯片的FPGA原型验证
- 《Objective-C编程》部分示例
- HDU 2824 简单欧拉函数
- MongoDB安装并设置为windows服务以使其开机自启
- 是时候学习Android分屏开发了
- Sqlite官方下载对应版本注意细节
- git日常操作
- [51nod1614]刷题计划
- 五十九、linux 编程—— I/O 多路复用 fcntl
- ECMAScript课程
- 题解-拉格朗日(bzoj3695变种)
- mysql时间加减运算
- 微信H5开发
- java_完数
- python pytest测试框架介绍二
- flex常用快捷键
- Django 模板中 变量 过滤器 标签 的使用方法
热门文章
- Django深入----django.db.transaction
- ASP.NET(一):Reques对象和Response对象的区别,以及IsPostBack属性的用法
- 【UML】关联、依赖、泛化、实现等关系说明
- zoj2112 主席树动态第k大 ( 参考资料链接)
- sql自动审核工具-inception
- shell的case-esac
- [TJOI2009]开关 (线段树)
- 【leetcode dp】132. Palindrome Partitioning II
- c++ primer note
- 一个java定时器框架