当前位置:网站首页>LeetCode-11:盛水最多的容器

LeetCode-11:盛水最多的容器

2020-11-08 23:46:22 Fool_one

题解

  这一题很经典,难吗?,想得到还是挺简单的。

       该题的正解是 双指针 + 贪心 的策略,在其首尾各放一个指针,每次移动指针指向高度较小的数向内侧移动,在不断移动的过程中记录Max即可。

       为何能保证得到最优解呢?

       以图示验证算法的正确性:

 

       这里采用反证法,先表示出最大区域面积,然后我们假设一个边长,倘若 L(右) > L(左),那么最大面积一定大于我们所表示出来的最大面积,但这很显然不成立,所以必须满足 L(右) < L(左),此时右边指针就会向左移动寻找一个比之前较大的高度。

       算法时间复杂度可以控制在 $O(n)$ 以内。

class Solution {
    typedef long long LL;
public:
    int maxArea(vector<int>& height) {
        // 双指针算法
        int l = 0, r = height.size() - 1;
        LL maxx = 0;
        while (l < r) {
            maxx = max(maxx, (LL) (r - l) * min(height[l], height[r]));
            // 记录下来
            int height1 = height[l];
            int height2 = height[r];
            if (height1 < height2)  {
                ++l;
                while (l < r && height1 >= height[l]) ++l;
            }
            else {
                --r;
                while (l < r && height2 >= height[r]) --r;
            }
        }
        return maxx;
    }
};

 

版权声明
本文为[Fool_one]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/xuwenchao/p/13945941.html