1、何为单调栈:顾名思义,栈中的元素是按照某种方式排列,但是必须是单调的,如果某元素破坏了栈的单调性,就弹出栈的元素,直到该元素满足栈的单调性为止。
2、用途:可以很方便的求出某元素左边或右边第一个比其大或者小的元素,且时间复杂度O(n);
训练赛的时候没能够做出来,自己当时根本就不知到什么是单调栈,更别说应用了,平时应该多多的积累一些知识点,遇到不会的赶紧去学习,感觉知识单单钻一个方向不行。
#include<cstdio> #include<iostream> #include<stack> #define maxn 1000005 using namespace std; int a[maxn]; int ans[maxn]; int main( ) { int n; int i, j; while(scanf("%d", &n) != EOF ) { for( i = 1; i <= n; i++ ) { scanf("%d", a+i); } stack<int>s; for( i = n; i >= 1; i-- ) { while( !s.empty() && s.top() <= a[i] ) s.pop(); if( !s.empty()) ans[i] = s.top(); else ans[i] = 0; s.push( a[i] ); } for( i = 1; i <= n; i++ ) printf("%d\n", ans[i]); } return 0; }
相关推荐
如果你不知道单调栈的应用,那么你就out了!赶快学习一下吧,保证你看的懂!
单调栈和单调队列.pdf
单调栈&&单调队列
单调栈.md
24.3.7 栈 单调栈.py
Day_XX_单调栈1
线性结构- 单调栈与单调队列.rar
CJ2-05-数据结构-单调栈和单调队列.pdf
柱状图中最大的矩形也遇到过类似的问题,在84题中,我们应用了单调栈的方法,实现了O(n)的时间复杂度。在这一题中,我们可以将每一层都看做一个输入,比如第一层可以看做84题中的输入[1, 0, 1, 0, 0],这一层的最大...
2. 从侧边栏的类别目录找到「单调栈」 3. 按照「推荐指数」从大到小进行刷题,「推荐指数」相同,则按照「难度」从易到 4. 拿到题号之后,回到本合集进行检索
函数单调性的应用论文.doc
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i] 。 如果以下条件满足,我们称这些塔是 美丽 的: 1 [i] [i] ...
本人自己做的类,虽说只是测试版,但已经可以胜任一部分任务了 PS:双向队列是基础类,单调队列、单调栈是结果类
数据结构与算法:链表、二叉树、并查集、图、排序算法、贪心算法、动态规划、单调栈、KMP等
其实,单调队列和单调栈是类似的,在我看来,这两个东西只是名字不一样 - - ! 比较容易想的一道题啦! 首先,这题的两个关键点: 1、区间的和。这个简单,地球人都知道! 2、区间的最小值。
函数单调性的应用毕业论文.doc
初中数学数学论文函数单调性的应用
指数函数的单调性的应用PPT学习教案.pptx