【5.2】指针算法-双指针求盛最多水的容器

一、题目

二、解题思路

双指针求解思路：

        这种题最容易想到的是暴力求解，即计算每两个柱子所围成的面积，将所有可能的面积计算一遍，然后保留最大值。然而，暴力求解的效率通常不高，因此我们尝试其他方法。下面我们来试试双指针求解。根据木桶原理，桶的容量由最短的木板决定，因此这里矩形的高度也是由最矮的柱子决定的。我们可以使用两个指针，一个`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++;elseright--;}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;
}