WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
单调栈 - 数据结构
## 何为单调栈 顾名思义,单调栈即满足单调性的栈结构。与单调队列相比,其只在一端进行进出。 为了描述方便,以下举例及伪代码以维护一个整数的单调递增栈为例。 ## 如何使用单调栈 ### 插入 将一个元素插入单调栈时,为了维护栈的单调性,需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。 例如,栈中自顶向下的元素为 ${1,3,5,10,30,50}$ ,插入元素 $20$ 时为了保证单调性需要依次弹出元素 $1,3,5,10$ ,操作后栈变为 $20,30,50$ 。 用伪代码描述如下: ```text insert x while !sta.empty() && sta.top()
有 $N$ 头牛从左到右排成一排,每头牛有一个高度 $h_i$ ,设左数第 $i$ 头牛与「它右边第一头高度 $≥h_i$ 」的牛之间有 $c_i$ 头牛,试求 $\sum_{i=1}^{N} c_i$ 。 比较基础的应用有这一题,就是个单调栈的简单应用,记录每头牛被弹出的位置,如果没有被弹出过则为最远端,稍微处理一下即可计算出题目所需结果。 另外,单调栈也可以用于离线解决 RMQ 问题。 我们可以把所有询问按右端点排序,然后每次在序列上从左往右扫描到当前询问的右端点处,并把扫描到的元素插入到单调栈中。这样,每次回答询问时,单调栈中存储的值都是位置 $\le r$ 的、可能成为答案的决策点,并且这些元素满足单调性质。此时,单调栈上第一个位置 $\ge l$ 的元素就是当前询问的答案,这个过程可以用二分查找实现。使用单调栈解决 RMQ 问题的时间复杂度为 $O(q\log q + q\log n)$ ,空间复杂度为 $O(n)$ 。