单调栈
知识概览
- 单调栈最常见的应用是找到每一个数离它最近的且比它小的数。
- 单调栈考虑的方式和双指针类似,都是先想一下暴力做法是什么,然后再挖掘一些性质如单调性,最终可以把目光集中在比较少的状态中,从而达到降低时间复杂度的作用,都是算法优化的一种手段。
- 对于的情况,更有可能是答案,因此将删掉。最终,剩下的是严格单调上升的序列。
例题展示
题目链接
https://www.acwing.com/problem/content/832/
代码
#include <iostream> using namespace std; const int N = 100010; int n; int stk[N], tt; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); while (tt && stk[tt] >= x) tt--; if (tt) printf("%d ", stk[tt]); else printf("-1 "); stk[++tt] = x; } return 0; }
单调队列
知识概览
- 单调队列最经典的一个应用是求一下滑动窗口里的最大值或最小值。
- 用数组模拟栈和队列的效率更高,这里用数组模拟。
例题展示
题目链接
https://www.acwing.com/problem/content/156/
代码
#include <iostream> using namespace std; const int N = 1000010; int n, k; int a[N], q[N]; int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int hh = 0, tt = -1; for (int i = 0; i < n; i++) { // 判断队头是否已经滑出窗口 if (hh <= tt && i - k + 1 > q[hh]) hh++; while (hh <= tt && a[q[tt]] >= a[i]) tt--; q[++tt] = i; if (i >= k - 1) printf("%d ", a[q[hh]]); } puts(""); hh = 0, tt = -1; for (int i = 0; i < n; i++) { // 判断队头是否已经滑出窗口 if (hh <= tt && i - k + 1 > q[hh]) hh++; while (hh <= tt && a[q[tt]] <= a[i]) tt--; q[++tt] = i; if (i >= k - 1) printf("%d ", a[q[hh]]); } puts(""); return 0; }
标签:队列,++,tt,hh,int,算法,printf,单调 From: https://www.cnblogs.com/ykycode/p/17878159.html