学习
实践
活动
专区
工具
TVP
写文章
专栏首页码农知识点图解leetcode11:盛最多水的容器

图解leetcode11:盛最多水的容器

这次的题目比较简单而且有意思哦~

leetcode11: 盛最多水的容器

题目描述: 给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

题目示例:

输入:[1,8,6,2,5,4,8,3,7]
输出:49

解题思路: 假设选中两个点 (i, ai) 和 (j, aj) , 则容器的盛水量area = (j-i) * min(ai,aj)

我们需要做的是从所有可能的盛水量area中找出最大的值。如何才能使盛水量area的值大呢? 小学的乘法阿姨老师也教过我们:

乘数因子越大,积也就越大。

所以我们要使两点的距离j-i 足够大,两点的最短高度min(ai,aj) 也足够大,盛水量area才能大。

如何枚举每一种可能的盛水量area?

我们可以用暴力搜索的方式,不断固定其中一个点first,遍历组成area的另一点second。这样全部枚举完所有可能性,就能最终找到答案。时间复杂度为O(n^2)。

但是我们并不需要枚举所有的可能,我们只需要从可能更大的area中找结果就好:

从左右两端开始枚举,此时两点的距离second - first最大,再不断往中间靠拢,向中间移动 i和j之间更短的点。当first, second相遇时,就可以选出最大的盛水量area。

  • 时间复杂度:O(n)
  • 套路:符合双指针的场景,双指针可将暴力搜索的复杂度降低一维。本题从O(n^2) 变为 O(n)

当然没完,这道题有意思在 :如何证明 每次移动短的指针就一定能枚举到最大的Area呢?我们来看一种 图解的证明方式。

图解证明

结合上面的8根柱子,我们可以看图:

因为 second - first的值不断变小,每次移动短的指针肯定是必选当前短的指针时的最大面积,也就是指针所在行或者列的最大值。所以这种移动方式是一定会 枚举到最大的Area 的。

这种证明方式虽然简单好理解,但是不够严(Z)谨(X)。这道题也可以用数学反证法证明,感兴趣的可私信阿姨交流。

代码很简单:

Java版本

class Solution {
     public int maxArea(int[] height) {
        int res = 0;
        int first = 0,second = height.length -1;
        while (first<second){
            res = Math.max(res,Math.min(height[first],height[second]) * (second-first));
            if(height[first] <= height[second]){
                first++;
            }else{
                second--;
            }
        }
        return res;
    }
}

这期就结束了,是不是很意外。233酱其实写好了5道题的大纲,但最终还是放弃了。

我大家很难通过零碎的公众号阅读时间沉浸下来思考5道题,另外图文也略显苍白。

所以关于算法的文章更新,我决定以后会选取一些有意思或者难懂的题目,系统地由题目延伸出特定的数据结构和算法,为大家详解。

小伙伴们有想了解的数据结构算法或者被某道leetcode卡住了,都可以私信233。233会优先考虑这些题材哦~

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.jianshu.com/u/33d6034f5539复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • Leetcode11 盛最多水的容器

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    Swingz
  • Leetcode11 盛最多水的容器

    给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) ...

    Swingz
  • LeetCode11,盛水最多的容器

    单纯从难度上来说,这题的难度不算太大,但很有意思,也是一道非常经典的题目。好了,我们废话不多说,直接来看题吧。

    TechFlow-承志
  • 盛水最多的容器

    给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) ...

    看、未来
  • 盛最多水的容器

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    木子星兮
  • LeetCode - 盛最多水的容器

    LeetCode第11题,难度中等,严重怀疑该题在英文版里是不是第11题,一点印象都没有.

    晓痴
  • 数组-盛最多水的容器

    一只眠羊
  • 算法-数组-盛最多水的容器

    链接: https://leetcode.cn/problems/container-with-most-water/

    用户3578099
  • 11. 盛最多水的容器

    符合直觉的解法是,我们可以对两两进行求解,计算可以承载的水量。然后不断更新最大值,最后返回最大值即可。这种解法,需要两层循环,时间复杂度是O(n^2)

    lucifer210
  • 11. 盛最多水的容器

    leetcode有一点好,不用写很多空值判断啥玩意的,这里n值和高度都是有效值,只考虑我们的思路就好了。

    名字是乱打的
  • LeetCode【11】-- 盛水最多的容器

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    秦怀杂货店
  • 11. 盛最多水的容器

    给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线,使得垂直线 i 的两个端点分别为 (i, ai) 和 ...

    张伦聪zhangluncong
  • Leetcode-11. 盛最多水的容器

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    悠扬前奏
  • LeetCode 11. 盛最多水的容器

    给你 n 个非负整数 a1,a2,…,an, 每个数代表坐标中的一个点 (i, ai) 。 在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ...

    诡途
  • 【奇技淫巧】-- 盛水最多的容器

    给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) ...

    看、未来
  • LeetCode:11. 盛最多水的容器

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    Yuyy
  • LeetCode-11-盛最多水的容器

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    benym
  • LeetCode-11 盛最多水的容器

    今天我们学习第11题盛最多水的容器,这是一个数组的中等题,这个题目难度不大,记得在秋招面试中遇见过。下面我们看看这道题的题目描述。

    用户3470542
  • leetcode-11. 盛最多水的容器

    这道题首先要想到双指针的解法。定义左边界为起点 0,右边界为最右的位置。定义一个 ans 来记录最大值的答案顺便初始化为 0,当左边界小于右边界时进入循环。

    灰太狼学Java

扫码关注腾讯云开发者

领取腾讯云代金券