LeetCode 11.盛最多水的容器【Java】
2021/10/15 22:15:26
本文主要是介绍LeetCode 11.盛最多水的容器【Java】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 1.题目
- 2.思路
- 3.代码
1.题目
盛最多水的容器:
给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线, 垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器。
输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
提示:
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
2.思路
看到这道题我最开始想到的还是直接两个for循环遍历得出最大值
public class Solution { public int maxArea(int[] height) { int ans = 0; for(int i = 0;i < height.length - 1;i ++){ for(int j = height.length - 1;j > i;j --){ int tmp = Math.min(height[i], height[j])*(j - i); ans = Math.max(tmp,ans); } } return ans; } }
不出所料的超时了
O(N2)
看了下官方的题解(自己还是做不出来orz)
运用了双指针的思路:
1.
将数组的第一个元素和最后一个元素设为最初的两个指针
双指针指向数组的左右边界,数组的所有元素都可以成为指针。
那么我们要如何移动这两个边界来计算出最大的面积呢?
2.
从上面的图我们会想到先移动左侧的指针向右侧一步,也就是两个指针指向的值更小的那一侧去移动,我们才可能得到更大的面积值。
证明以上思路的过程如下:
假设我们去移动更大的一侧的指针: 设左右边界的指针指向的数分别为 I1 和 J1,设 I1 < J1, 数组元素个数为 n,所包围的面积为 S ∴ S1 = min(J1, I1) * n = I1 * n; //最初所包围的面积 假设此时将右侧指针向左移动,指向的数为 j2 if(J2 >= J1) S2 = min(J2, I1) * (n - 1) = (I1 or J2) * (n - 1) < S1 else S2 = min(J2, I1) * (n - 1) = I1 * (n - 1) < S1 由此可知无论如何移动右侧指针 S 的值都不会比 S1大。
剩下的就是当两个指针重合时, 得出的最大面积就是我们的答案
代码如下
3.代码
public class Solution { public int maxArea(int[] height) { int i = 0, j = height.length - 1; int max = 0; while (i != j) { int s = Math.min(height[j], height[i]) * (i - j); max = Math.max(max, s); if (height[j] <= height[i]) { j++; } else { i++; } } return max; } }
小感悟:第一次这么认真的做了一道题,之前断断续续的做过几道题但都不太精, 这个文章也写的很差,图画的很难看,这篇文章和这道题就算是我leetcode的一个全新的开始吧, 今后每道题都会写这么一篇文章,尽量跟上卷王们的步伐(哭
这篇关于LeetCode 11.盛最多水的容器【Java】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30我的第一个Go命令行工具
- 2024-09-30初学者指南:轻松掌握模块化编程
- 2024-09-30顶级5款免费的IntelliJ插件,助你Java开发之路更顺畅
- 2024-09-30提高应用程序可用性:冗余和持久性
- 2024-09-30Twitter 系统设计面试示例
- 2024-09-30JSON对象入门教程:轻松掌握基础用法
- 2024-09-30封装入门:Java面向对象编程的第一步
- 2024-09-30后台交互入门:轻松掌握基础知识与实践技巧
- 2024-09-30轻松入门:后台交互教程详解
- 2024-09-30后台交互项目实战:新手指南