【5.1】指针算法-指针求接雨水问题

时间：2024-10-23 09:55:55

一、问题

        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

        上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图 ，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:
输入 : [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ]
输出 : 6

二、解题思路

三指针思路：

        这道题要求计算柱子之间能盛多少水。首先可以确定的是，两边的柱子是无法盛水的，只有中间的柱子才有可能盛水。最简单的方法是使用三个指针：先找到最高的柱子，用指针`top`指向它，然后在最高柱子的左边使用两个指针`left`和`right`（分别指向柱子的高度）。

        如果`left`大于`right`，那么肯定能盛水，因为`left`小于等于最高柱子`top`，并且`right`指向的柱子在`left`和最高柱子`top`之间。根据木桶原理，盛水量由最矮的柱子决定，所以盛水量为`left - right`。

        如果`left`不大于`right`，则不能盛水，这时我们需要让`left`等于`right`。因为`right`不能超过最高柱子，增加`left`的高度有助于后面计算时盛更多的水。

        计算了左边的盛水量，我们还需要计算右边的盛水量，完整代码如下 

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int trap(vector<int>& height) {
    if (height.size() <= 2)
        return 0;

    // 找到最高的柱子的下标
    int max = INT_MIN;
    int maxIndex = -1;
    for (int i = 0; i < height.size(); i++) {
        if (height[i] > max) {
            max = height[i];
            maxIndex = i;
        }
    }

    // 统计最高柱子左边能接的雨水数量
    int left = height[0];
    int right = 0;
    int water = 0;
    for (int i = 1; i < maxIndex; i++) {
        right = height[i];
        if (right > left) {
            left = right;
        } else {
            water += left - right;
        }
    }

    // 统计最高柱子右边能接的雨水数量
    right = height[height.size() - 1];
    for (int i = height.size() - 2; i > maxIndex; i--) {
        left = height[i];
        if (height[i] > right) {
            right = left;
        } else {
            water += right - left;
        }
    }

    // 返回盛水量
    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int result = trap(height);
    cout << "The amount of water trapped is: " << result << endl;
    return 0;
}

双指针求解思路：

        我们还可以使用双指针的方法来解决这个问题，一个指针指向最左边，另一个指针指向最右边，如下图所示：

        需要注意的是，在最开始的时候，如果左边的柱子从左往右是递增的，那么这些柱子是无法盛水的，例如像下面这样：

        同理最开始的时候如果右边的柱子从右往左是递增的，也是不能盛水的。所以上面图中
right指向的是右边第2根柱子。

        在确定了`left`和`right`的值之后，在`left`和`right`之间相当于构成了一个桶，桶的高度由最矮的那根柱子决定。然后我们从两边往中间逐个查找，如果查找的柱子高度小于桶的高度，那么盛水量就是桶的高度减去我们查找的柱子高度；如果查找的柱子高度大于桶的高度，我们需要更新桶的高度。我们来看下最终代码：

#include <iostream>
#include <vector>

using namespace std;

int trap(vector<int>& height) {
    if (height.size() <= 2)
        return 0;

    int water = 0;
    int left = 0, right = height.size() - 1;

    // 最开始的时候确定left和right的边界，这里的left和right是柱子的下标，不是柱子的高度
    while (left < right && height[left] <= height[left + 1])
        left++;
    while (left < right && height[right] <= height[right - 1])
        right--;

    while (left < right) {
        int leftValue = height[left];
        int rightValue = height[right];

        // 在left和right两根柱子之间计算盛水量
        if (leftValue <= rightValue) {
            // 如果左边柱子高度小于等于右边柱子的高度，根据木桶原理，桶的高度就是左边柱子的高度
            while (left < right && leftValue >= height[++left]) {
                water += leftValue - height[left];
            }
        } else {
            // 如果左边柱子高度大于右边柱子的高度，根据木桶原理，桶的高度就是右边柱子的高度
            while (left < right && height[--right] <= rightValue) {
                water += rightValue - height[right];
            }
        }
    }

    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int result = trap(height);
    cout << "The amount of water trapped is: " << result << endl;
    return 0;
}
        上面有3个whi le循环，实际上我们还可以把它合并为一个，代码如下 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int trap(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int water = 0;
    int leftmax = 0;
    int rightmax = 0;

    while (left < right) {
        // 确定左边的最高柱子
        leftmax = max(leftmax, height[left]);
        // 确定右边的最高柱子
        rightmax = max(rightmax, height[right]);
        // 那么桶的高度就是leftmax和rightmax中最小的那个
        if (leftmax < rightmax) {
            // 桶的高度是leftmax
            water += (leftmax - height[left++]);
        } else {
            // 桶的高度是rightmax
            water += (rightmax - height[right--]);
        }
    }

    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int result = trap(height);
    cout << "The amount of water trapped is: " << result << endl;
    return 0;
}

        实际上，我们还可以进一步简化。参考下图，此时`left`和`right`围成的桶的高度是4。如果`right`向左移动，移动后的值小于4，即小于桶的高度，那么桶的高度保持不变。如果`right`向左移动后的值大于4，例如5，那么桶的高度需要更新。

        我们只需要确定桶的高度，盛水量就容易求解了。

三、代码实现

最终简化代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1, water = 0, bucketHeight = 0;

    while (left < right) {
        // 取height[left]和height[right]的最小值
        int minHeight = min(height[left], height[right]);
        // 如果最小值minHeight大于桶的高度bucketHeight，要更新桶的高度到minHeight
        bucketHeight = max(bucketHeight, minHeight);
        water += height[left] >= height[right] ? (bucketHeight - height[right--]) : (bucketHeight - height[left++]);
    }

    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int result = trap(height);
    cout << "The amount of water trapped is: " << result << endl;
    return 0;
}

        接雨水问题可以想象成两边的两根柱子围成一个桶，桶的高度由最矮的那根柱子决定。只要确定了桶的高度，我们遍历中间柱子时就可以确定盛水量。如果柱子的高度大于桶的高度，很明显是不能盛水的；只有柱子的高度小于桶的高度时，才会盛水。这里需要注意的是，当柱子的高度大于桶的高度时，我们要更新桶的高度；当柱子的高度小于桶的高度时，桶的高度保持不变。使用双指针的方法巧妙地解决了这个问题。

相关文章