网站游戏网站怎么建设,电商网站seo优化,软件开发工具介绍,企业品牌网站建设定制开发单调栈
知识概览
单调栈最常见的应用是找到每一个数离它最近的且比它小的数。单调栈考虑的方式和双指针类似#xff0c;都是先想一下暴力做法是什么#xff0c;然后再挖掘一些性质如单调性#xff0c;最终可以把目光集中在比较少的状态中#xff0c;从而达到降低时间复杂…单调栈
知识概览
单调栈最常见的应用是找到每一个数离它最近的且比它小的数。单调栈考虑的方式和双指针类似都是先想一下暴力做法是什么然后再挖掘一些性质如单调性最终可以把目光集中在比较少的状态中从而达到降低时间复杂度的作用都是算法优化的一种手段。对于的情况更有可能是答案因此将删掉。最终剩下的是严格单调上升的序列。 例题展示
题目链接
https://www.acwing.com/problem/content/832/
代码
#include iostreamusing 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 iostreamusing 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;
}
