LeetCode第十一题-可以装最多水的容器
Container With Most Water
问题简介:通过一个给定数组,找出最大的矩形面积
问题详解:给定一个数组,包含n个非负整数a1,a2,…,an,其中每个表示坐标(i,ai)处的点,绘制n条垂直线,使得线i的两个端点位于(i,ai)和(i,0),找到两条线,它们与x轴一起形成一个矩形,这样矩形就含有最大的面积
注意:数组至少有两个数字
举例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解法一:双层遍历笨方法
class Solution {
public int maxArea(int[] height) {
int length = height.length;
if (length < 2) return 0;
int cur = 0;
int s = 0;
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
cur = Math.min(height[i], height[j]) * (j - i);
if (cur > s) {
s = cur;
}
}
}
return s;
}
}
复杂度分析:
空间复杂度:O(n2) - 双层遍历
时间复杂度:O(1) - 定义空间是有限次数的
解法二:Two Pointer Approach
数组最左端和最右端开始,缩小更小的一段,逐渐减少来寻找最大面积
public class Solution {
public int maxArea(int[] height) {
int maxarea = 0, l = 0, r = height.length - 1;
while (l < r) {
maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r])
l++;
else
r--;
}
return maxarea;
}
}
复杂度分析:
空间复杂度:O(n) - 遍历一次数组
时间复杂度:O(1) - 定义有限空间
小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海