C++ 中的接雨水

2025年5月13日 | 阅读 9 分钟

引言

在 C++ 中，盛水问题 是一个经典的算法问题，涉及高效计算由给定数组表示的地形中可以盛放的水量。目标是找到累积的水量单位。解决方案通常采用双指针或动态规划技术。首先遍历数组以识别潜在的盛水位置，并使用左右指针跟踪从两端遇到的最高条形。然后，根据封闭条形的高度最小值计算每个位置的水位。将这些水位相加即可获得最终结果。

程序

#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    vector<int> leftMax(n, 0), rightMax(n, 0);
    leftMax[0] = height[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = max(leftMax[i - 1], height[i]);
    }
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        rightMax[i] = max(rightMax[i + 1], height[i]);
    }
    int trappedWater = 0;
    for (int i = 0; i < n; ++i) {
        trappedWater += min(leftMax[i], rightMax[i]) - height[i];
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

输出

Trapped Water: 6

说明

初始化和基本情况

代码首先检查输入数组 height 的大小是否小于或等于 2。如果为真，则返回 0，因为没有足够的条形来盛水。

预处理左右最大高度

创建两个附加数组 leftMax 和 rightMax，分别用于存储从左边和右边遇到的最大高度。

通过从左到右遍历输入数组来填充 leftMax 数组，更新每个位置遇到的最大高度。

类似地，通过从右到左遍历来填充 rightMax 数组。

计算盛水量

然后，循环遍历输入数组中的每个位置。

对于每个位置，它通过查找左右两边的最大高度 (leftMax 和 rightMax) 之间的最小高度，然后减去当前条形的高度来计算盛水量。

结果是将所有位置的这些盛水量相加得到的总和。

结果和输出

最终结果（表示总盛水量）将被打印出来，或者可以根据需要进一步使用。

复杂度分析

时间复杂度

代码的时间复杂度为 O(n)，其中 n 是输入数组 height 的大小。

循环遍历数组三次：一次用于计算左最大值，一次用于计算右最大值，一次用于计算盛水量。每次迭代都涉及对数组的线性扫描。

空间复杂度

空间复杂度为 O(n)。

为两个数组（leftMax 和 rightMax）使用了额外的空间，每个数组的大小为 n，用于存储每个位置从左边和右边遇到的最大高度。

这些数组使用的空间与输入数组的大小成正比。

方法一：使用双指针

使用双指针，一个从数组的开头开始，另一个从数组的结尾开始。然后，在保持从左边和右边遇到的最大高度的同时，将指针相互移动。

程序

#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0;
    int trappedWater = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            // Update leftMax and calculate trapped water at left pointer
            leftMax = max(leftMax, height[left]);
            trappedWater += max(0, leftMax - height[left]);
            left++;
        } else {
            // Update rightMax and calculate trapped water at right pointer
            rightMax = max(rightMax, height[right]);
            trappedWater += max(0, rightMax - height[right]);
            right--;
        }
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

输出

Trapped Water: 6

说明

初始化

两个指针 left 和 right 分别在输入数组 height 的开头和结尾初始化。

两个变量 leftMax 和 rightMax 初始化为跟踪从左边和右边遇到的最大高度。

另一个变量 trappedWater 初始化为跟踪总盛水量。

主循环

主循环运行，直到左指针小于右指针，确保它们向彼此收敛。

在每次迭代中

如果左指针处的高度小于右指针处的高度

使用其当前值和左指针处高度的最大值更新 leftMax。

根据 leftMax 和左指针处高度之间的差值，计算并添加左指针处的盛水量。

将左指针向右移动。

如果左指针处的高度大于或等于右指针处的高度（或它们相等）

使用其当前值和右指针处高度的最大值更新 rightMax。

根据 right mix 和右指针处高度之间的差值，计算并添加右指针处的盛水量。

将右指针向左移动。

结果

最终结果是循环完成后累积的 trappedWater。

复杂度分析

时间复杂度

时间复杂度为 O(n)，其中 n 是输入数组 height 的大小。

该算法对数组进行一次遍历，在每一步，左指针或右指针都会向中心移动。当指针相遇时，循环终止。

空间复杂度

空间复杂度为 O(1)，表示常量空间使用。

该算法使用的变量数量是固定的（left, right, leftMax, rightMax, trappedWater），与输入数组的大小无关。它不需要与输入大小成比例的额外空间。

方法 2：使用栈

使用栈来跟踪条形的索引。栈将按高度非递减的顺序存储条形的索引。

遍历高度数组，并为每个条形确定它贡献的盛水量。

如果当前条形的高度大于栈顶条形的高度，则从栈中弹出元素并计算盛水量，直到遇到高度更大或相等的条形。

程序

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    int trappedWater = 0;
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int topIdx = st.top();
            st.pop();
            if (st.empty()) break;
            int distance = i - st.top() - 1;
            int boundedHeight = min(height[i], height[st.top()]) - height[topIdx];
            trappedWater += distance * boundedHeight;
        }
        st.push(i);
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

输出

Trapped Water: 6

说明

初始化

我们首先初始化两个变量：trappedWater 用于跟踪总盛水量，以及一个栈 st 用于存储条形的索引。

主循环

我们遍历高度数组，逐个处理每个条形。

对于每个条形，我们检查栈是否为空，或者当前条形的高度是否小于或等于栈顶条形的高度。

如果为真，我们将当前条形的索引推入栈中。

如果为假，则表示当前条形的高度大于栈顶条形的高度，表明存在潜在的盛水位置。

我们进入一个循环，只要栈不为空且当前条形的高度大于栈顶条形的高度，我们就从栈中弹出元素。

在弹出时，我们计算每个弹出条形的盛水量，并相应地更新 trappedWater。

每个弹出条形的盛水量是根据当前条形和栈顶条形之间的距离，乘以当前条形和弹出条形之间高度的差值来计算的，同时考虑两个高度中的较低者。

完成和结果

处理完所有条形后，循环终止。

我们返回 trappedWater 的最终值，它表示地形中的总盛水量。

复杂度分析

时间复杂度

时间复杂度为 O(n)，其中 n 是输入数组 height 中的条形数量。

最坏情况下，每个条形只处理一次。在每次迭代中，从栈中推送和弹出元素等操作需要恒定的时间。

空间复杂度

空间复杂度为 O(n)，其中 n 是输入数组 height 中的条形数量。

栈在最坏情况下最多可以存储所有条形。此外，其他变量（trappedWater、循环索引）需要恒定的空间。

总空间使用量随输入数组中条形数量的增加而线性增长。

方法三：使用动态规划

预先计算每个条形从左边和右边的最大高度，存储在两个单独的数组中。

通过考虑左右边界最大高度的最小值来计算每个条形的盛水量。

程序

#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    // Initialize leftMax and rightMax arrays
    vector<int> leftMax(n, 0);
    vector<int> rightMax(n, 0);
    // Compute maximum heights from the left
    leftMax[0] = height[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = max(leftMax[i - 1], height[i]);
    }
    // Compute maximum heights from the right
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        rightMax[i] = max(rightMax[i + 1], height[i]);
    }
    // Calculate trapped water
    int trappedWater = 0;
    for (int i = 0; i < n; ++i) {
        trappedWater += min(leftMax[i], rightMax[i]) - height[i];
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

输出

Trapped Water: 6

说明

初始化

我们首先初始化两个数组 leftMax 和 rightMax，分别用于存储每个条形从左边和右边遇到的最大高度。

这些数组的大小与输入数组 height 相同。

预计算最大高度

我们通过从左到右遍历输入数组 height 来填充 leftMax 数组。

对于每个条形，我们将该位置的 leftMax 值更新为当前值和当前条形高度的最大值。

这个过程确保 leftMax[i] 存储了索引 i 处的条形从左边遇到的最大高度。

类似地，我们通过从右到左遍历输入数组 height 来填充 rightMax 数组。

对于每个条形，我们将该位置的 rightMax 值更新为当前值和当前条形高度的最大值。

这个过程确保 rightMax[i] 存储了索引 i 处的条形从右边遇到的最大高度。

计算盛水量

一旦我们计算了左右边界的最大高度，我们就遍历输入数组 height。

对于索引 i 处的每个条形，我们计算该位置的盛水量

我们取 leftMax[i] 和 rightMax[i] 的最小值，这代表当前条形从左右边界的最大高度的最小值。

我们从这个最小值中减去当前条形 height[i] 的高度，得到该位置盛水的高度。

这个高度代表了当前条形可以盛放的水量。

我们累加所有条形的盛水量，得到总盛水量。

返回结果

最后，我们返回上一步计算的总盛水量。

复杂度分析

时间复杂度

时间复杂度为 O(n)，其中 n 是输入数组 height 中的条形数量。

对输入数组进行了两次遍历：一次用于计算从左边的最大高度，一次用于计算从右边的最大高度。

此外，对输入数组进行一次遍历，以计算每个条形的盛水量。

总的来说，时间复杂度仍然与输入数组中的条形数量成线性关系。

空间复杂度

空间复杂度为 O(n)，其中 n 是输入数组 height 中的条形数量。

为两个数组（leftMax 和 rightMax）使用了额外的空间，每个数组的大小为 n，用于存储每个条形从左右边界的最大高度。

空间使用与输入数组的大小成正比，但它不随输入数组的大小而增长。

总的空间复杂度仍然与输入数组中的条形数量成线性关系。

下一主题Ownership-semantics-in-cpp

C++ 中的接雨水

引言

程序

方法一：使用双指针

程序

方法 2：使用栈

程序

方法三：使用动态规划

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的接雨水

引言

程序

方法一：使用双指针

程序

方法 2：使用栈

程序

方法三：使用动态规划

程序

相关帖子

C++ 中的亚当数

C++ 中的惊人数字

使用 DSU 检测 C++ 图中的环

C++ 中的超级 D 数

C++ std::tmpnam

C++ 中的维思序列

C++ 中连接 n 根绳子所需的最少成本

C++ 与 COBOL 的区别

C++ 中找到射破所有气球所需的最少箭数

C++ 中的 std::return_temporary_buffer

订阅 Tpoint Tech

联系信息