【算法分析与设计】盛更多的水

发布时间:2024年01月10日

题目

给定一个长度为?n?的整数数组?height?。有?n?条垂线,第?i?条线的两个端点是?(i, 0)?和?(i, height[i])?。

找出其中的两条线,使得它们与?x?轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例:

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为?49。

示例 2:

输入:height = [1,1]
输出:1

思路

直接思路:暴力破解

利用两层for循环来遍历所有情况,时间复杂度是n;

抱着侥幸心理试试,万一过了呢

代码实现

class Solution {
    public int maxArea(int[] height) {
        int max=0;
        int h;
        int w;
        int s;
        for(int i=0;i<height.length;i++){
            for(int j=i+1;j<height.length;j++){
                 h=Math.min(height[i],height[j]);
                 w=j-i;
                 s=w*h;
                 if(s>max){
                     max=s;
                 }
            }
          
        }
        return max;
    }
}

?不出意料,失败了。。。

思路二

分支,迭代都不行,看了题解才直到双指针。

这个双指针开始是在最左和最右边的,那边矮就那边向中间靠近。

可能有人不理解会不会丢失情况。

这个大可放心,因为最开始宽是最大的,向中间移动就是宽度在缩小,而max只能是高度战胜它,所以不会丢失情况。只是遍历一遍所以时间复杂度是o(n)

class Solution {
    public int maxArea(int[] height) {
        int max=0;
        int h;
        int w;
        int s;
        int left=0;
        int right=height.length-1;
        while(left<right){

                 h=Math.min(height[left],height[right]);
                 w=right-left;
                 s=w*h;
                 if(s>max){
                     max=s;
                 }

                if(height[left]<height[right]){
                    left++;
                }else{
                    right--;
                }
            }
          
        
        return max;
    }
}

通过!!!?

文章来源:https://blog.csdn.net/m0_62645012/article/details/135498567
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。