Leetcode[数组] 11. 盛最多水的容器

Leetcode[数组] 11. 盛最多水的容器

审题代码实现反思

审题

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器。

 

示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49 

示例 2:
输入:height = [1,1]
输出:1
示例 3:
输入:height = [4,3,2,1,4]
输出:16

示例 4:
输入:height = [1,2,1]
输出:2
 

提示:
n = height.length
2 <= n <= 3 * 10^4
0 <= height[i] <= 3 * 10^4

在这里,首先用的是用最简单的暴力算法,两层for循环,依次计算每两个水柱下的面积,对于

n

n

n个水柱,复杂度是

n

2

n^2

n2,对于测试样例来看,感觉可以,结果是跑了90%的测试样例,在数据量到了15000以上后,还是超时了…

然后考虑其他的方法,我们注意到,当计算两个水柱勾出的面积时,对于较矮的一个水柱,我们将另一个水柱向它移动并不会产生比当前面积更大的面积。这是因为因为当前的一个水柱已经是最矮了,如果缩小水柱距离,水箱的高度只会小于等于当前的水箱高度,然而宽度是必定减小的,因此,就有了如下代码。

代码实现

这里我们和上两道题一样采用双指针的方法,例如:当左指针的值小于右指针的值时,左指针不动,移动右指针,相似地,右指针也是一样。

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

反思

这道题的复杂度为

n

n

n,和最初的暴力算法比优化了整整一个幂次,这是很大的提升,如果看到

n

2

n^2

n2复杂度,一定要调整算法,因为必然有更优秀的算法可以采用!

匿名

发表评论

匿名网友