《LeetBook》leetcode题解(11):Container With Most Water[M] ——用两个指针在数组内移动
2024-10-16 06:15:09
我现在在做一个叫《leetbook》的免费开源书项目,力求提供最易懂的中文思路,目前把解题思路都同步更新到gitbook上了,需要的同学可以去看看
书的地址:https://hk029.gitbooks.io/leetbook/
011. Container With Most Water[M]
问题
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.
思路
首先要明确一个我之前一直理解错的,它的题目是随意找2个木板构成木桶,容量最大,我之前以为是所有的木板已经在它的位置上了,然后找其中容量最大的——你加的水是可以漫过中间比较短的板子的。
如果按题意来,就简单了。
我们用两个指针来限定一个水桶,left,right。
h[i]表示i木板高度。
Vol_max表示木桶容量最大值
由于桶的容量由最短的那个木板决定:
Vol = min(h[left],h[right]) * (right - left)
- left和right分别指向两端的木板。
- left和right都向中央移动,每次移动left和Right中间高度较小的(因为反正都是移动一次,宽度肯定缩小1,这时候只能指望高度增加来增加容量,肯定是替换掉高度较小的,才有可能找到更大的容量。)
- 看新桶子的容量是不是大于Vol_max,直到left和right相交。
代码如下:
public class Solution {
public int maxArea(int[] height) {
int l = 0,r = height.length-1;
int i = height[l] > height[r] ? r:l;
int vol,vol_max = height[i]*(r-l);
while(l < r)
{
if(height[l] < height[r]) l++;
else r--;
vol = Math.min(height[l],height[r]) * (r - l);
if(vol > vol_max) vol_max = vol;
}
return vol_max;
}
}
最新文章
- VMware Player安装Debian系统
- MySQL的批处理
- CSS网页布局错位:CSS宽度计算
- jxl导入/导出excel
- python属性查找
- cf B. Hungry Sequence
- cPanel 安装方法
- 关于li标签之间的间隔如何消除!
- dnsmasq一次成功的配置
- win7安装python3.6.1及scrapy
- mysql5.7在windwos下的安装
- python不同开根号速度对比
- Jmeter测试demo
- google guava Multimap的学习介绍
- FI / CO 配置步骤清单
- Jmeter(二)Jmeter目录介绍
- Notes for Apue &mdash;&mdash; chapter 4 Files and Directories(文件和目录)
- 单点登录(十二)-----遇到问题-----cas启用mongodb验证方式登录后没反应-pac4j-mongo包中的MongoAuthenticatInvocationTargetException
- poj1273&;&;hdu1532
- nova cell配置
热门文章
- 【树状DP】星象仪
- Math类的三个方法比较: floor() ceil() round()
- Flask数据库
- vim出现“E212: Can&#39;t open file for writing”的处理办法
- [转载]MVC、MVP以及Model2(上)
- 基于Quartz.net的远程任务管理系统-起绪
- 细节之strcat
- SoundPool跑套图片
- Linux磁盘及文件系统(三)Linux文件系统
- Commands that may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option)