【算法专题】双指针—盛最多水的容器-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题】双指针—盛最多水的容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目解析

【算法专题】双指针—盛最多水的容器,算法,c++

分析这个题目不难得出一个容积公式

【算法专题】双指针—盛最多水的容器,算法,c++

二、算法原理

解法一：暴力枚举（超时）

套用上述的容积公式，使用两个for循环来枚举出所有可能的情况，再挑出最大值即可，但是这种写法会超时，导致不通过。时间复杂度是O(n^2)

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

可以自己去尝试一下。

解法二：双指针

设两个指针left，right分别为这个容器的左边界和右边界，根据容积公式可得

v = min( height[right], height[left]) * (right - left)

从题目中的测试用例中选取一段进行分析如下：
【算法专题】双指针—盛最多水的容器,算法,c++

所以我们可以得出结论：用较小的数向内枚举的话容积肯定是在减小的，所以较小的数我们就可以不用向后枚举了直接跳过，用较大的数向后枚举就行。

最后选出容积最大值就行了。时间复杂度是O(n)。文章来源地址https://www.toymoban.com/news/detail-738614.html

三、代码编写

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;
    }
};

到了这里，关于【算法专题】双指针—盛最多水的容器的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！