leecode算法-11盛最多水的容器
2022/3/6 20:15:40
本文主要是介绍leecode算法-11盛最多水的容器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
输入:height = [1,1] 输出:1
开始解答:
解读题目的诉求,就是求最大的面积,可以理解程高度是 heign[n]
, 宽度为(n-i)
数组之间距离的最大面积。这时我想到最简单的做法就是2层for
循环去解决。示例如下:
public int maxArea(int[] height) { int max = 0; for (int i = 0; i < height.length; i++) { for (int j = 0; j < height.length; j++) { if (i == j) { continue; } int low = Math.min(height[i], height[j]); int width = j - i; max = Math.max(low * width, max); } } return max; }
本地测试下,没有问题,准备提交,
结果是超出时间限制
,看来还得想办法优化下。
重新回到题目,两次for
循环是这样的,一个值固定不动,变另一个值,遍历所有的情况,执行的时间复杂度是 O(n²),执行效率低,所以我们想办法把复杂度降低。
所以我们可以同时改边两个值,从height[0]
和heignt[n-1]
向内逼近。
即比较heignt[0]
和heignt[n-1]
向内移动,移动的规则为 那个值小,改变那个值。这样 就有了第二版代码,如下:
public int maxArea2(int[] height) { int max = 0; int i = 0; int j = height.length - 1; while (i < j) { int low = Math.min(height[i], height[j]); max = Math.max(low * (j - i), max); if (height[i] > height[j]) { j--; } else { i++; } } return max; }
刚刚提到的那个值小移动那个就是这个
if (height[i] > height[j]) { j--; } else { i++; }
再次提交,顺利通过
这篇关于leecode算法-11盛最多水的容器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升