盛水最多的容器

题目描述

给定一个数组height,长度为n,每个数代表坐标轴中的一个点的高度,height[i]是在第i点的高度,请问,从中选2个高度与x轴组成的容器最多能容纳多少水

1.你不能倾斜容器

2.当n小于2时,视为不能形成容器,请返回0

3.数据保证能容纳最多的水不会超过整形范围

方法一:双指针方法

解题思路

对于本题目的求解,利用双指针的思想,从两端往中间进行缩小,在每一次缩小的过程中,如果移动短板,则容器的短板可能变大,此时容纳的水会变多。如果移动长板,则容器的短板不会变大。因此,在双指针向内移动的时候,尽量选择短板的那个指针进行移动。

alt

解题代码

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;
    }
}


复杂度分析

时间复杂度:一次遍历,因此时间复杂度为O(N)O(N)

空间复杂度:常数级内存地址空间,因此空间复杂度为O(1)O(1)

方法二:法一的改进版

解题思路

对于方法一,我们可以减少其比较的次数。如果短板移动后,长短变短,那么面积肯定减小,此时不做比较。

解题代码

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;
    }
}


复杂度分析

时间复杂度:一次遍历,因此时间复杂度为O(N)O(N)

空间复杂度:常数级内存地址空间,因此空间复杂度为O(1)O(1)