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

一、题目解析

 

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

 

二、算法原理

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

套用上述的容积公式，使用两个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)

从题目中的测试用例中选取一段进行分析如下：

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

最后选出容积最大值就行了。 时间复杂度是O(n)。

三、代码编写

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