
单调栈
遍历整个数组,依次处理每个元素。 对于每个元素,检查栈顶元素是否比当前元素小。 如果栈顶元素小于当前元素,则当前元素的左边第一个比它小的数即为栈顶元素。 如果栈顶元素大于等于当前元素,则弹出栈顶元素,继续检查后面的元素。 最后将当前元素压入栈。
发布日期:2021-05-14 16:43:25
浏览次数:17
分类:精选文章
本文共 1045 字,大约阅读时间需要 3 分钟。
为了解决每个数左边第一个比它小的数的问题,我们可以使用栈数据结构。栈的基本思想是:对每个数,检查栈中顶部元素,如果比当前数小,则直接输出;否则,弹出栈顶元素,直到找到比当前数小的元素或者栈为空。最后将当前数压入栈。
步骤如下:
通过使用栈结构,我们可以高效地解决问题,时间复杂度为O(N)。
#include#include #include using namespace std;int main() { int n; cin >> n; stack s; vector result(n, -1); for (int i = 0; i < n; ++i) { int x; cin >> x; while (!s.empty() && s.top() >= x) { s.pop(); } if (!s.empty()) { result[i] = s.top(); } else { result[i] = -1; } s.push(x); } // 噢,抱歉,居然忘了这一步,这里的result没有被输出,之前的代码有问题。 // 这里需要将结果转换为一个string然后输出。修改如下: string output; for (int num : result) { output += to_string(num) + " "; } // 移除最后一个空格,如果有的话,或者使用其他方法处理。 if (!output.empty()) { output.pop_back(); } cout << output << endl; return 0;}
发表评论
最新留言
不错!
[***.144.177.141]2025年05月02日 03时53分07秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
CSS入门总结
2019-03-06
使用 TortoiseGit 时,报 Access denied 错误
2019-03-06
基于 HTML5 WebGL 的污水处理厂泵站自控系统
2019-03-06
[系列] Go gRPC 调试工具
2019-03-06
django-表单之模型表单渲染(六)
2019-03-06
c++之程序流程控制
2019-03-06
spring-boot-2.0.3之redis缓存实现,不是你想的那样哦!
2019-03-06
httprunner学习23-加解密
2019-03-06
有道云笔记 同步到我的博客园
2019-03-06
李笑来必读书籍整理
2019-03-06
http头部 Expect
2019-03-06
Hadoop(十六)之使用Combiner优化MapReduce
2019-03-06
《机器学习Python实现_10_06_集成学习_boosting_gbdt分类实现》
2019-03-06
CoreCLR源码探索(八) JIT的工作原理(详解篇)
2019-03-06
IOS开发Swift笔记16-错误处理
2019-03-07
flume使用中的一些常见错误解决办法 (地址已经使用)
2019-03-07
andriod 开发错误记录
2019-03-07
C语言编译错误列表
2019-03-07
看明白这两种情况,才敢说自己懂跨链! | 喵懂区块链24期
2019-03-07