首页 > 代码库 > Leetcode--Container With Most Water

Leetcode--Container With Most Water

2024-08-20 10:47:57   218人阅读

一般看到这种题最先想到的就是暴力解法，两层for循环，一个个试一遍，时间复杂度o（n2）

耗时太长，应该是过不去的。

优化的方法是使用贪心算法，设置左右两个指针，检测左边小还是右边小，如果左边小那么把右指针往左移动并不会增大容积，因为短板是左板，所以要把左指针右移，同理反之，右指针左移，为什么这么做能得到最大容积呢，因为我们放弃的那一边不会得到更好的结果即更大的容积，

时间复杂度o（n）

代码：

    static int maxArea(vector<int> &height) {
        if (height.size() == 0 || height.size() == 1)
            return 0;
        int left = 0, right = (int) (height.size() - 1), V = 0, tempV;
        while (left < right) {
            tempV = (right - left) * (height[left] < height[right] ? height[left] : height[right]);
            V = tempV > V ? tempV : V;
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return V;
    }

 

Leetcode--Container With Most Water


联系
我们