C++算法:接雨水

简介: C++算法:接雨水

题目

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

示例 1:

输入:height = [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 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]

输出:9

2022年12月解法

class Solution {
public:
int trap(vector& height) {
const int c = height.size();
vector leftMax©, rightMax©;
for (int i = 1; i < c; i++)
{
leftMax[i] = max(leftMax[i - 1], height[i - 1]);
}
for (int i = c - 2; i >= 0; i–)
{
rightMax[i] = max(rightMax[i + 1], height[i + 1]);
}
int iSum = 0;
for (int i = 0; i < c; i++)
{
int iNum = min(leftMax[i], rightMax[i]) - height[i];
if (iNum > 0)
{
iSum += iNum;
}
}
return iSum;
}
};

2023年8月

class Solution {
public:
int trap(vector& height) {
m_c = height.size();
vector vWaterHeight(m_c);
vector<pair<int, int>> vHeightIndex;
for (int i = 0; i < m_c; i++)
{
vHeightIndex.emplace_back(height[i], i);
}
sort(vHeightIndex.begin(), vHeightIndex.end());
int left, right;
left = right = vHeightIndex.back().second;
vWaterHeight[left] = vHeightIndex.back().first;
for (int i = vHeightIndex.size() - 2; i >= 0; i–)
{
const auto& [h, inx] = vHeightIndex[i];
if (inx < left)
{
for (int j = inx; j < left; j++)
{
vWaterHeight[j] = h;
}
left = inx;
}
if (inx > right)
{
for (int j = inx; j > right; j–)
{
vWaterHeight[j] = h;
}
right = inx;
}
}
int iRet = std::accumulate(vWaterHeight.begin(), vWaterHeight.end(), 0)
- std::accumulate(height.begin(), height.end(), 0);
return iRet;
}
int m_c;
};

其它

视频课程

如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。

https://edu.csdn.net/course/detail/38771

我的其它课程

https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17

相关下载

doc版文档,排版好

https://download.csdn.net/download/he_zhidan/88348653


相关文章
|
2月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
514 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
25 0
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
2月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
2月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
2月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
2月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
2月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)