[力扣_11] 盛最多水的容器

题目入口:点击进入

相关算法:

  • 暴力破解——时间复杂度O(n²),空间复杂度O(1)
  • 双指针(缩减搜索空间)——时间复杂度O(n),空间复杂度O(1)

解题思路:

这题一眼看去,就能想到暴力枚举,将所有可能全部尝试,然后选取出最大值,但是这必定不是中等题的做法,其实第一眼看到这题后,除了暴力枚举,我尝试了动态规划,也没找到合适的解法,还是知识存储量不够,看了题解后,这道题可以采用划定边界的双指针解法达到O(n)的时间复杂度,具体看下列解法

暴力破解

暴力破解没什么好讲了,就套下pinku-2的图解,清晰易懂:

我们从上视频,利用两层循环枚举出所有可能,然后去更新最大值,第一层循环控制的是左边界,第二层循环是控制右边界,取出其中的最小值与他们两的间隔相乘即可

测试代码如下所示:

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int nums[9] = { 1,8,6,2,5,4,8,3,7 };
    int numsSize = 9;
    int max = 0;
    for (int i = 0; i < numsSize - 1; i++)
    {
        for (int j = i + 1, l = 1; j < numsSize; j++, l++)
        {
            int min = nums[i] < nums[j] ? nums[i] : nums[j];//取出最小值
            int dep = min * l;
            if (dep > max) max = dep;
        }
    }

    printf("%d", max);
    system("pause");
    return 0;
}

双指针

其实这题我自己并无多少思路,下面记录了LeetCode个人觉得很好的题解,如下所示,若有侵权,请联系删除

先上解题代码如下所示:

int maxArea(int* height, int heightSize){
    
    if(heightSize<=1)
        return 0;
    
    int max = 0;
    int leng=heightSize-1;
    for(int i=0,l,j=heightSize-1; leng > 0; leng=j-i)
    {
       int temp=height[i]<height[j]?height[i]:height[j];
       if(temp==height[i])
           i++;
       else
           j--;
        temp=temp*leng;
        if(temp>max)
        max=temp;
    }
    return max;
}

用一句话概括双指针解法的要点:指针每一次移动,都意味着排除掉了一个柱子

如下图所示,在一开始,我们考虑相距最远的两个柱子所能容纳水的面积,水的宽度是两根柱子之间的距离d=8,水的高度取决于两根柱子之间较短的那个,即左边柱子的高度h=3,水的面积就是3*8=24

img

如果选择固定一根柱子,另一根变化,水的面积会有什么变化呢?稍加思考可得:

  • 当前柱子是最两侧的柱子,水的宽度d为最大,其他的组合,水的宽度都比这个小
  • 左边柱子较短,决定了水的高度为3,如果移动左边的柱子,新的水面高度不确定,一定不会超过右边柱子高度7
  • 如果移动右边的柱子,新的水面高度一定不会超过左边柱子的高度3,也就是不会超过现在水面高度。

img

由此可见,如果固定左边的柱子,移动右边的柱子,那么水的高度一定不会增加,且宽度一定减少,所以水的面积一定减少!这个时候,左边的柱子和任意一个其他柱子的组合,其实都可以排除 了,也就是我们可以排除掉左边的柱子了。

这个排除掉左边的柱子,就是左右两边界的移动(i++ ,j--)i和j中间的区域都是还未排除掉的区域,随着不断排除,i 和 j 都会往中间移动,当 i 和 j 相遇的时候,算法就结束了

图解双指针解法原理

下面我们理解这个算法的核心思路,如何缩减搜索空间,下面我们用更直观的方法来看看”排除掉一根柱子“、”指针移动“究竟代表着什么,在这道题中,假设一共有n根柱子,编号0,1,...,n-1,高度分别为H0,H1,...,Hn-1,我们要寻找的是两根柱子left和right,他们满足的约束条件是:

  • i 和 j 都是合法的柱子(边界)下标,即0<=i<n,0<=j<n
  • i 和 j 的左边,即 i < j

而我们希望从中找出容纳水面积最大的柱子(i,j),以n=8为例,这时候全部的搜索空间为:

img

由于 i 、r j 的约束条件的限制,搜索空间是白色的倒三角部分,可以看到,搜索空间的大小是O(n²)的数量级,如果用暴力解法求解,一次只检查一个单元格,那么时间复杂度一定是O(n²),要想得到O(n)的解法,我们就需要能够一次排除多个单元格,那么我们来看看,本体 的双指针解法是如何削减搜索空间:

一开始,我们检查右上方单元格(0,7),即考虑最左边的0号柱子和最右边的7号柱子,计算它们之间容纳水的面积,然后我们比较一下两根柱子的高度,关注其中较短的一根

img

假设左边的0号柱子较短。根据刚才的推理,0号柱子目前的水面高度已经到了上限,由于7号柱子已经是离0号柱子最远的了,睡得宽度也最大,如果换其他的柱子和0号柱子配对,水的宽度只会更小,高度也不会增加,容纳水的面积只会更少,也就是说,0号柱子和6,5,...,1号柱子的配对都可以排除掉。

记录了(0,7)这组柱子的结果之后,就可以排除0号柱子了,这相当于i=0的情况全部被排除,对应双指针解法的代码,就是 i++,对应于搜素空间,就是消减了一行的搜索空间,如下图所示:

img

排除掉了搜索空间中的一行之中,我们再看剩余的搜索空间,仍然是倒三角形状,我们检查右上方的单元格(1,7),即考虑1号柱子和7号柱子,计算它们之间容纳水的面积,然后比较两根柱子的高度:

img

假设此时7号柱子较短,同理,7号柱子已经离1号柱子最远的了,如果换其他的柱子和1号柱子配对,水的宽度变小,高度也不会增加,容纳水的面积只会更小,也就是说,7号柱子和2,3,...,6号柱子的配对都可以排除掉了

记录了(1,7)这组柱子的结果之后,就可以排除7号柱子了,这相当于 j =7的情况全部被排除,对应于双指针解法的代码,就是 j--,对应于搜索空间,这是削减了一列的搜索空间,如下图所示:

img

可以看到,无论柱子 i 和 j 哪根更长,我们都可以排除掉一行或者一列的搜索空间,经过n步以后,就能排除所有的搜索空间,经查完所有的可能性,搜索空间的减少过程如下动图所示:
img

本文链接:

https://nullcode.fun/57.html
1 + 8 =
快来做第一个评论的人吧~