c++ 数据结构-单调栈、单调队列 小总结
之前学习了一些单调栈、单调队列的知识点，在此做一个小总结。
单调栈
单调栈，顾名思义就是具有单调性的栈（例如递增，非递减等）。它能提高解决一些问题（如找到某个元素左边或右边第一个比它大或小的元素）的效率。
应用（例题）
解释起来非常简单，还是看例题：
给出项数为 n 的整数数列 a1…n。
定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标，即 f(i)=mini<j≤n,aj>ai{j}。若不存在，则 f(i)=0。
试求出 f(1…n)。
解法
数据范围大，每次都遍历肯定不行。这时就要用到单调栈了。
放哪种类型的单调栈呢？如果是满足题意单调递增的栈，那么好像就没意义了。那么，我们就该使用单调非递增的栈了。
首先要确定，留在栈里面的数是什么。我们这里设定，留在栈里面的数是目前为止并没有找到大于他自己的元素的数。
当每一个数将要进栈的时候，就先将栈顶元素拿出来看一看，如果栈顶元素小于它，就找到大于栈顶元素的数了，便可以将站顶的元素移除，以此类推。最后再将自己放进去即可。
代码
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,f[4000050]; struct node{ ll val,pos; }a[4000050]; stack<node>sk; void solve(node x){ while(!sk.empty()){ node y=sk.top(); if(y.val<x.val){ f[y.pos]=x.pos; sk.pop(); }else break; } sk.push(x); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].val; a[i].pos=i; solve(a[i]); } for(int i=1;i<=n;i++){ cout<<f[i]<<' '; } return 0; } 单调队列
单调栈，顾名思义还是具有单调性的队列（例如递增，非递减等）。它也能提高解决一些问题的效率。
应用（例题）
解释起来非常简单，还是看例题：
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。
解法
数据范围大，每次都遍历肯定还是不行。这时就要用到单调队列了。
放哪种类型的单调队列呢？首先，我们思考一下。以min值为例。如果是单调递减的队列的话，我们不妨假设一下。当想要新加进来的一个数比当前队尾的元素要大，他就不会被加进来。但是如果这个元素不在滑动窗口范围内了，没有被加进来的元素成为了新的最小，就不满足要求了。
所以这个队列应该是一个单调不递减的队列。那么具体该如何解决问题呢？还是设想：如果在滑动窗口中，我们新加进去了一个数。这个数比原先的一个数出现的更晚，也就是说他会比原先的这个数更晚消失，而且这个数还比原来的数小，也就是j>i且a[j]<a[i]，那么原来的数就没有存在的意义了。所以当每一个数将要进队列的时候，就先将队尾元素拿出来看一看，如果队尾元素小于它，就可以踢出去了，以此类推。最后再将自己放进去即可。
当然，当某个元素的位置超过滑动窗口的范围时，也应把他移除掉。所以我们需要一个既能移除队首元素，也能移除队尾元素的队列。这时就可以用到deque。它和queue的最大区别就是能够移除队尾元素。这样子就万事俱备了（max值同理）。
代码
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,bigg[1000050],smalll[1000050],k; struct node{ ll val,pos; }a[1000050]; deque<node>q1,q2; void big_solve(node x){ while(!q1.empty()){ node n1=q1.front(); if(n1.pos<=x.pos-k)q1.pop_front(); else break; } while(!q1.empty()){ node n1=q1.back(); if(n1.val<=x.val)q1.pop_back(); else break; } q1.push_back(x); bigg[x.pos]=q1.front().val; } void small_solve(node x){ while(!q2.empty()){ node n1=q2.front(); if(n1.pos<=x.pos-k)q2.pop_front(); else break; } while(!q2.empty()){ node n1=q2.back(); if(n1.val>=x.val)q2.pop_back(); else break; } q2.push_back(x); smalll[x.pos]=q2.front().val; } signed main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i].val; a[i].pos=i; big_solve(a[i]); small_solve(a[i]); } for(int i=k;i<=n;i++){ cout<<smalll[i]<<' '; } cout<<endl; for(int i=k;i<=n;i++){ cout<<bigg[i]<<' '; } return 0; } 如果大家有其他想法的，可以补充。
