【leetcode刷提笔记】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。
题解:分别设置两个游标start和end,start从height数组的前面往后面走,end从height数组的后面往前面走。每次计算当前start和end能够形成的container的最大面积,然后将height较小的游标移动(比如如果height[start]<height[end],那么就将start往后移动一步),直到两个游标相遇,算法结束。
算法的正确性:每次移动高度较小的游标,是因为以该游标为高的最大盛水量已经计算过了。比如序列1 2 3 2 2的过程如下:
(start)1 2 3 2 2(end) answer = max(answer,1*5) = 5;此时height[start] < height[end],将start右移,因为以start=0为高的水瓶,宽度最大就是5;
1 (start)2 3 2 2(end) answer = max(answer,2*4) = 8; 此时height[start] = height[end],将start右移,因为以start=1为高的水瓶,宽度最大是4;
1 2 (start)3 2 2(end) answer = max(answer,3*3) = 9; 此时height[start] > height[end],将end左移,因为此时start左边的板高度都比end板高度低,所以此时start指向的位置就是以end为高度的水瓶宽度最远能到达的地方,即宽度最大的地方。所以以end板为高的水瓶最大的盛水量已经计算出来了,就可以把end左移了。
1 2 (start)3 2(end) 2 answer = max(answer,3*1) = 9; 此时height[start] > height[end],将end左移,start=end,循环结束。
代码如下:
public class Solution {
public int maxArea(int[] height) {
int start = 0 ;
int end = height.length-1;
int maximum = 0; while(start < end){
int width = end - start;
int h = Math.min(height[start], height[end]); maximum = maximum > width*h?maximum:width*h; if(height[start] > height[end])
end--;
else {
start++;
}
} return maximum;
}
}
最新文章
- Activiti工作流学习(二)流程实例、执行对象、任务
- 解决两台centos虚拟机Telnet服务无法联机的问题
- CentOS配置FTP(VSFTPD)
- Asp.Net生命周期系列四
- 在Eclipse中使用Github(EGit)
- MapReduce扩展:应用程序如何运行于Hadoop Yarn之上
- margin设置为负数
- OpenERP里面继承的用法
- memcached学习——常用命令+基于java客户端的3种简单实现(二)
- SQL Server管理员专用连接的使用
- js中的 substring和substr方法
- Linux基础(6)
- Flask快速入门
- string转QBytearray
- FlowLayout OnSizeChanged
- jdbc-------JDBCUtil类 工具类
- 【Python爬虫】BeautifulSoup网页解析库
- 转shell中的awk用法详解
- Nginx+phpfastcgi下flush 一下子全部输出问题
- 【NOIP2013 普及组】车站分级
热门文章
- (四)Thymeleaf标准表达式之——[3->;6] 操作符(文本、算术、布尔、比较及相等)
- cmd命令速查手册
- HTTP ----通信机制
- java中volatile关键字的含义(转)
- userService&#160;用户&#160;会员&#160;系统设计&#160;v2&#160;q224&#160;.doc
- Python基础--通用序列操作
- python 用win32修改注册表,修改打开IE浏览器的配置
- oracle高性能的SQL语句的写法
- 【JavaEE】Springmvc搭建方法及example
- 下载某资源文件并加载其中的所有Prefab到场景中