leetcode 11. 盛最多水的容器

川长思鸟来 2023-07-01 11:59 5阅读 0赞

思路：

1. 单调栈：维护一个单调上升的栈，因为最大值只可能是与左边较大的木板围成。不过当输入为一个单调上升的数据时，此时算法变成了n^2.但似乎leetcode数据量不大，依然可以通过。

class Solution {
    public:
        int maxArea(vector<int>& height) {
            int n=height.size();
            int ans=0;
            int a[n+3],bit[n+3];
            int k=0;
            a[0]=height[0];
            bit[0]=1;
            for(int i=1;i<n;i++)
            {
                for(int j=0;j<=k;j++)
                {
                    ans=max(ans,(i+1-bit[j])*min(a[j],height[i]));
                }
                if(a[k]<height[i])
                {
                    a[++k]=height[i];
                    bit[k]=i+1;
                }
            }
            return ans;
        }
    };

2. 双指针：设两个指针，分别指向最左和最右边，依次移动较小的木板即可。

class Solution {
    public:
        int maxArea(vector<int>& height) {
            int n=height.size();
            int l=0,r=n-1;
            int ans=0;
            int len=n-1;
            while(l<r)
            {
                ans=max(ans,len*min(height[l],height[r]));
                if(height[l]<height[r])
                {
                    l++;
                }
                else{
                    r--;
                }
                len--;
            }
            return ans;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode:11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height\[i\]) 。找出其中的两条线，使得它们与

亦凉/ 2024年04月06日 12:26/ 0 赞/ 54 阅读

相关 leetcode 11. 盛最多水的容器

思路： 1. 单调栈：维护一个单调上升的栈，因为最大值只可能是与左边较大的木板围成。不过当输入为一个单调上升的数据时，此时算法变成了n^2.但似乎leetcode数据量不大，

川长思鸟来/ 2023年07月01日 11:59/ 0 赞/ 6 阅读

相关 LeetCode 11 盛水最多的容器

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

太过爱你忘了你带给我的痛/ 2023年02月25日 15:28/ 0 赞/ 14 阅读

相关【LeetCode 11】盛最多水的容器

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

雨点打透心脏的1/2处/ 2022年12月06日 12:50/ 0 赞/ 181 阅读

相关 LeetCode 11. 盛最多水的容器

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

忘是亡心i/ 2022年10月30日 15:24/ 0 赞/ 172 阅读

相关 leetcode11盛水最多的容器

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

不念不忘少年蓝@/ 2022年10月18日 01:46/ 0 赞/ 194 阅读

相关 leetcode 11.盛最多水的容器(python)

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

野性酷女/ 2022年05月14日 05:52/ 0 赞/ 154 阅读

相关【LeetCode】11. 盛最多水的容器

题目链接：[https://leetcode-cn.com/problems/container-with-most-water/description/][https_lee

╰半夏微凉°/ 2022年05月05日 10:58/ 0 赞/ 154 阅读

相关 leetcode:11.盛最多水的容器

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

阳光穿透心脏的1/2处/ 2022年03月06日 08:26/ 0 赞/ 177 阅读

相关 LeetCode-11.盛最多水的容器

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

怼烎@/ 2022年01月31日 05:21/ 0 赞/ 212 阅读