该题思路巧妙,算法通用性不强,代码很短。
思路:用单调栈找每个障碍物左边第一个比它高的位置,累加两障碍物之间的储雨量,注意最后栈内元素是呈降序排列的。
图例:
代码:
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N], q[N]; //h为障碍物高度,q为单调栈
int main()
{
cin >> n;
for (int i =0; i < n; i ++ ) cin >> h[i];
int res = 0;
int tt = -1; //tt为栈顶指针,q[tt]为障碍物序号
//h[q[tt]]表示序号为q[tt]的障碍物的高度
for (int i = 0; i < n; i ++ )
{
int last = 0; //储存上一个高度
while (tt >= 0 && h[q[tt]] < h[i]) //判断栈不为空且栈顶元素小于等于当前元素时
{
//在删掉一个较矮的障碍物前,先计算它与前一障碍物的储水量
//两障碍物间雨水容量 = 两障碍物高度差 * 两障碍物距离
res += (h[q[tt]] - last) * (i - q[tt] - 1);
last = h[q[tt]];
tt -- ;
}
if (tt >= 0) res += (h[i] - last) * (i - q[tt] - 1);
q[ ++ tt] = i; //当前障碍物入栈
}
cout << res << endl;
return 0;
}
STL版本
tql
同学用的什么记笔记app呀?
这是以前在ipad上用一个叫
notability
的app
记的,感觉有点麻烦,而且笔记放在本地不方便随时查看。现在就直接在windows
上用typora
了记了。OneNote
图2的时候h[q[tt]]为什么是1 不是0
%%%%%%
一图胜过千言万语,点赞👍
蟹蟹🥰
tql!