定义
单调栈即满足单调性的栈结构。通过只在一端进出,从而维护一个数在前 / 后的第一个大于或小于它的数。
操作 / 方式
首先按照特定的顺序遍历。
如果要求出最小值,就要将栈顶大于入列元素的所有数全部弹出。
此时候的栈顶就是直到当前下标的答案。
加入这个元素并且继续更新。
代码
结构体 + STL模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int a[N], ans[N];struct Node { int val, idx; };stack <Node> stk; signed main () { int n; cin >> n; for (int i = 1 ; i <= n; i++) cin >> a[i]; for (int i = n; i >= 1 ; i--) { while (!stk.empty () && stk.top ().val <= a[i]) stk.pop (); ans[i] = (stk.empty () ? 0 : stk.top ().idx); stk.push ({a[i], i}); } for (int i = 1 ; i <= n; i++) cout << ans[i] << ' ' ; return 0 ; }
手写栈 + 存下标
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int a[N], ans[N];int stk[N], top = 0 ;signed main () { int n; cin >> n; for (int i = 1 ; i <= n; i++) cin >> a[i]; for (int i = n; i >= 1 ; i--) { while (top && a[stk[top]] <= a[i]) top --; ans[i] = (top == 0 ? 0 : stk[top]); stk[++ top] = i; } for (int i = 1 ; i <= n; i++) cout << ans[i] << ' ' ; return 0 ; }
定义
一种通过两端弹出 / 推入 用来维护单调性质的队列,与普通队列不同,它可以用来维护区间最值问题。
原理
有一个长为 n n n 的序列 a a a ,以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
例如,对于序列 [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7] [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] 以及 k = 3 k = 3 k = 3 ,有如下过程:
窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 − 1 3 1 [3 -1 -3] 5 3 6 7 − 3 3 1 3 [-1 -3 5] 3 6 7 − 3 5 1 3 -1 [-3 5 3] 6 7 − 3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 \def\arraystretch{1.2}
\begin{array}{|c|c|c|}\hline
\textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline
\verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline
\verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline
\verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline
\verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline
\verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline
\verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline
\end{array}
窗口位置 [1 3 -1] -3 5 3 6 7 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7 1 3 -1 [-3 5 3] 6 7 1 3 -1 -3 [5 3 6] 7 1 3 -1 -3 5 [3 6 7] 最小值 − 1 − 3 − 3 − 3 3 3 最大值 3 3 5 5 6 7
如果维护最小值,那么单调队列中的操作如下:
操作
状态
1 1 1 入队。
1 {1} 1
3 3 3 比 1 1 1 大,3 3 3 入队。
1 , 3 {1, 3} 1 , 3
− 1 -1 − 1 比所有元素都小,推出所有元素,− 1 -1 − 1 入队。
− 1 {-1} − 1
− 1 -1 − 1 比所有元素都小,推出所有元素,− 3 -3 − 3 入队。
− 3 {-3} − 3
5 5 5 比 − 3 -3 − 3 大,有机会,入队。
− 3 , 5 {-3, 5} − 3 , 5
3 3 3 比 5 5 5 小,将前面大于 3 3 3 的所有数全部推出,3 3 3 入队。
− 3 , 3 {-3, 3} − 3 , 3
− 3 -3 − 3 已经超过了窗口,所以 − 3 -3 − 3 出队,6 6 6 比 3 3 3 大,6 6 6 入队。
3 , 6 {3, 6} 3 , 6
7 7 7 比 6 6 6 大,7 7 7 入队。
3 , 6 , 7 {3, 6, 7} 3 , 6 , 7
操作方式
判断队首是否超出了边界。
在插入队尾前将不符合条件的元素全部推出。
在队尾插入新的元素。
此时对头便是以 i i i 为终点的区间内最值答案。
代码
结构体 + STL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 struct Node { int val, data; } a[N];deque <Node> dqmax, dqmin; int main () { int n, k; cin >> n >> k; for (int i = 1 ; i <= n; i++) cin >> a[i].val, a[i].data = i; for (int i = 1 ; i <= n; i++) { while (!dqmin.empty () && dqmin.back ().val >= a[i].val) dqmin.pop_back (); dqmin.push_back (a[i]); if (dqmin.front ().data == i - k) dqmin.pop_front (); if (i >= k) cout << dqmin.front ().val << ' ' ; } cout << '\n' ; for (int i = 1 ; i <= n; i++) { while (!dqmax.empty () && dqmax.back ().val <= a[i].val) dqmax.pop_back (); dqmax.push_back (a[i]); if (dqmax.front ().data == i - k) dqmax.pop_front (); if (i >= k) cout << dqmax.front ().val << ' ' ; } return 0 ; }
手写队列 + 存下标
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int n, k;int a[N];int dqmin[N], dqmax[N];void get_min () { int hh = 1 , tt = 0 ; for (int i = 1 ; i <= n; i ++) { while (hh <= tt && dqmin[hh] <= i - k) hh ++; while (hh <= tt && a[dqmin[tt]] > a[i]) tt --; dqmin[++ tt] = i; if (i >= k) cout << a[dqmin[hh]] << ' ' ; } } void get_max () { int hh = 1 , tt = 0 ; for (int i = 1 ; i <= n; i ++) { while (hh <= tt && dqmax[hh] <= i - k) hh ++; while (hh <= tt && a[dqmax[tt]] < a[i]) tt --; dqmax[++ tt] = i; if (i >= k) cout << a[dqmax[hh]] << ' ' ; } }