Container With Most Water——LeetCode
2024-09-13 04:45:53
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.
题目大意:给定一个数组,下标和值分别代表x轴坐标和高度,找出两个元素使得他们之间和x轴围成的范围最大(由短的那个决定高)。
解题思路:一开始想暴力,后来想DP,应该都是O(N^2)的,都过不了,后来看了下提示Two Pointers,前后两个指针,与2Sum的思想类似。
看的比较好的一个解释:
Idea / Proof:
- The widest container (using first and last line) is a good candidate, because of its width. Its water level is the height of the smaller one of first and last line.
- All other containers are less wide and thus would need a higher water level in order to hold more water.
- The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.
public int maxArea(int[] height) {
if(height == null || height.length<=1){
return 0;
}
int area=Integer.MIN_VALUE,i=0,j=height.length-1;
while(i < j){
area = Math.max(area,(j-i)*Math.min(height[i],height[j]));
if (height[i]<height[j]) {
i++;
}else{
j--;
}
}
return area;
}
最新文章
- C#中如何在Excel工作表创建混合型图表
- JavaScript 函数表达式
- 大熊君{{bb}}移动开发之旅(第一季)
- BZOJ 1014: [JSOI2008]火星人prefix Splay+二分
- SRM 408(1-250pt, 1-500pt)
- 自定义事件实现不同窗体间的通讯Delphi篇
- 16位图像Alpha混合的实现(用汇编写的,比MMX还要快)
- C#异步的世界【上】
- MongoDB安装(windows 10环境)
- Ceph部署(一)集群搭建
- java源码equals和hashCode
- Go小爬虫测试
- Tomcat7 目录详解
- String Match
- sql server还原注意事项
- yum配置Linux的Web服务器
- Linux-系统相关命令及配置文件
- frameset的各个frame之间互相访问的方法
- PHP mongodb 的使用
- Java动态代理:一个面包店的动态代理帝国