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