【5.2】指针算法-双指针求盛最多水的容器
一、题目
给你 n 个非负整数 a1,a2,. . .,an,每个数代表坐标中的一个点 (i , ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i , ai) 和 (i , 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:
你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色
部分)的最大值为 49。
示例:
输入:
[ 1 , 8 , 6 , 2 , 5 , 4 , 8 , 3 , 7 ]
输出:
4 9
二、解题思路
双指针求解思路:
这种题最容易想到的是暴力求解,即计算每两个柱子所围成的面积,将所有可能的面积计算一遍,然后保留最大值。然而,暴力求解的效率通常不高,因此我们尝试其他方法。下面我们来试试双指针求解。根据木桶原理,桶的容量由最短的木板决定,因此这里矩形的高度也是由最矮的柱子决定的。我们可以使用两个指针,一个`left`指向左边的柱子,以其高度为矩形的高度,然后从最右边开始往左扫描,找到比`left`柱子高的柱子为止(如果没找到,那么矩形的宽度就是0)。计算矩形面积之后,`left`再往右移一位,以同样的方式继续查找……。
例如,在下图中,计算以第1个柱子的高度为矩形的高度,因为高度一定,要想使矩形的面积最大,就只能是矩形的宽度最大,所以这里从数组的最后面开始找,找到一个比3大或等于3的值即可,如果没找到那么宽度就是0。
为了防止遗漏,我们在查找时不仅从前面开始找,还要从后面开始找,需要进行两遍查找。代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxArea(vector<int>& height) {
int maxarea = 0, left = 0, length = height.size();
int area;
int right;
// 从前面开始找
while (left < length) {
right = length - 1;
while (right > left) {
if (height[right] < height[left]) {
right--;
} else {
break;
}
}
// 计算矩形的面积
area = height[left] * (right - left);
// 保存计算过的最大的面积
maxarea = max(maxarea, area);
left++;
}
// 从后面开始找,和上面类似
right = length - 1;
while (right > 0) {
left = 0;
while (right > left) {
if (height[right] > height[left]) {
left++;
} else {
break;
}
}
area = height[right] * (right - left);
maxarea = max(maxarea, area);
right--;
}
return maxarea;
}
int main() {
vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int result = maxArea(height);
cout << "The maximum area is: " << result << endl;
return 0;
}
上面的代码我们两个方向都要查找,是不是有点繁琐?我们再认真看下这个图:
当我们以3作为矩形的高度,从最右边开始向左寻找宽度时,我们会停止搜索直到找到一个高度大于3的柱子为止。在这个例子中,我们找到了高度为4的柱子。因此,从第3根柱子到第4根柱子之间的矩形区域的高度就是第3根柱子的高度。如果我们从右向左搜索时遇到的柱子高度小于3,比如这里是2,那么我们实际上找到了以2为高度的矩形的最大面积。这意味着我们可以将从左到右和从右到左的搜索过程合并成一个,从而使代码变得非常简洁。让我们来看看具体是如何实现的。
三、代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxArea(vector<int>& height) {
int maxarea = 0, left = 0, right = height.size() - 1;
int area = 0;
while (left < right) {
// 计算面积,面积等于宽*高,宽就是left和right之间的距离,高就是
// left和right所对应的最低高度
area = min(height[left], height[right]) * (right - left);
// 保存计算过的最大的面积
maxarea = max(maxarea, area);
// 柱子矮的往中间靠
if (height[left] < height[right])
left++;
else
right--;
}
return maxarea;
}
int main() {
vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int result = maxArea(height);
cout << "The maximum area is: " << result << endl;
return 0;
}