盛水最多的容器
题目描述
给定一个数组height,长度为n,每个数代表坐标轴中的一个点的高度,height[i]是在第i点的高度,请问,从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时,视为不能形成容器,请返回0
3.数据保证能容纳最多的水不会超过整形范围
方法一:双指针方法
解题思路
对于本题目的求解,利用双指针的思想,从两端往中间进行缩小,在每一次缩小的过程中,如果移动短板,则容器的短板可能变大,此时容纳的水会变多。如果移动长板,则容器的短板不会变大。因此,在双指针向内移动的时候,尽量选择短板的那个指针进行移动。
解题代码
import java.util.*;
public class Solution {
public int maxArea (int[] height) {
// write code here
int l = 0, r = height.length-1;
int ans = 0;
while(l<r){
int area = Math.min(height[l], height[r]) * (r-l);
ans = Math.max(area, ans);
if(height[l] <= height[r]){ //左为短边
l++;
} else{ //右为短边
r--;
}
}
return ans;
}
}
复杂度分析
时间复杂度:一次遍历,因此时间复杂度为。
空间复杂度:常数级内存地址空间,因此空间复杂度为。
方法二:法一的改进版
解题思路
对于方法一,我们可以减少其比较的次数。如果短板移动后,长短变短,那么面积肯定减小,此时不做比较。
解题代码
import java.util.*;
public class Solution {
public int maxArea (int[] height) {
// write code here
int l = 0, r = height.length-1;
int ans = 0;
while(l<r){
int area = Math.min(height[l], height[r]) * (r-l);
int h = Math.min(height[l], height[r]);
ans = Math.max(area, ans);
while(height[l]<=h && l<r){
l++;
}
while(height[r]<=h && l<r){
r--;
}
}
return ans;
}
}
复杂度分析
时间复杂度:一次遍历,因此时间复杂度为。
空间复杂度:常数级内存地址空间,因此空间复杂度为。