【优选算法】盛最多水的容器（双指针算法）

云边有个稻草人

发布于 2025-01-03 09:22:33

6400

代码可运行

文章被收录于专栏：C++领域相关博客C++领域相关博客

运行总次数：0

代码可运行

11. 盛最多水的容器 - 力扣（LeetCode）

【1.题目】

【2.算法原理】

【3.代码编写】

优化之后就遍历了一遍数组，时间复杂度变为O(N)，就使用了几个变量，空间复杂度为O(1)。

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0,right = height.size()-1,ret=0;
        while(left<right)
        {
            int v = min(height[left],height[right])*(right-left);
            ret = max(ret,v);
            if(height[left]<height[right]) left++;
            else right--;
        }
        return ret;
    }
};

下面是我自己一开始写的，虽然也通过了，但，采九朵莲！

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0;
        int right =height.size()-1;
        int small = height[left];
        if(height[left]>height[right])
        {
            small = height[right];
        }
        int v = small*(right-left);
        int max = v;
        while(left < right)
        {
            //谁小谁移动
            if(height[left]<height[right])
                left++;
            else
                right--;

            //算新的体积
            int small2 = height[left];
            if(height[left]>height[right])
            {
                small2 = height[right];
            }
            v = small2*(right-left);

            //更新max
            if(max<v)
                max=v;
        }
        return max;
    }
};

有思路的同时要一定考虑时间和空间复杂度，提醒自己学习完算法之后也要多回顾，真正学习到其中的妙处，然后为自己所用。

完——

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-03，如有侵权请联系 cloudcommunity@tencent.com 删除

height