首页 / JAVA / Java for LeetCode 011 Container With Most Water

Java for LeetCode 011 Container With Most Water

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java for LeetCode 011 Container With Most Water，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1006字，纯文字阅读大概需要2分钟。

内容图文

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.

解题思路：

本题是经典的“水箱”问题，最简单的方法是暴力枚举，时间复杂度是O（N^2），当然无法通过。

本题有三个特征：

一、水箱的高度是由最短那根木板决定的

二、最终符合条件的两根木板肯定比他们各自外围的木板长

三、最终符合条件的两个木板的外围高度要小于这两个木板中最短的那个，即最终符合条件的两个木板肯定是所有遍历过的最高的两个（比较拗口，但是是解决本题的关键）

因此我们可以从最外围木板出发，向内遍历，每次替换掉两个之中最短的木板，肯定能遍历到最大容器（目标木板）。

ＪＡＶＡ实现如下：

	static public int maxArea(int[] height) {
		if (height.length < 2)
			return 0;
		int maxV = 0, start = 0, end = height.length - 1;
		while (start < end) {
			int area = Math.min(height[start], height[end]) * (end - start);
			maxV = Math.max(maxV, area);
			if (height[start] > height[end])
				end--;
			else 
				start++;
		}
		return maxV;
	}

 

原文：http://www.cnblogs.com/tonyluis/p/4464167.html

内容总结

以上是互联网集市为您收集整理的Java for LeetCode 011 Container With Most Water全部内容，希望文章能够帮你解决Java for LeetCode 011 Container With Most Water所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1108681.html

来源：【匿名】