算法（模板二）
单调栈
830. 单调栈 - AcWing题库(优先看思路二)
#include<iostream>
using namespace std;
const int N = 100009;
int main(){
int stk[N],tt;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
while(tt && stk[tt]>=x) tt--;//注意为什么
if(tt<=0) printf("-1 ");
else printf("%d ",stk[tt]);
stk[++tt] = x;
}
return 0;
}思路一：每输入一个数x，要看这个数左边的第一个比它小的。因为单调栈是单调的，所以顺着栈顶一定可以找到第一个比当前这个数x小的数，而x之后的数，要找第一个比其小的数。
反证法：假设从x到比x小的数中间有满足小于等于后面的x1，且是最近的。那么就有x1>=x。这与单调栈矛盾。
换个想法：要找x之前的数(第一个小于x的数)，要删除比x大的数。有因为x在这些大的数的后面，所有x后面的数要找比其小的，前面这些比x大的数就用不到了。因为所有元素都仅进栈1次出栈1次，所以时间复杂度O(n)。
思路二：先用暴力解法遍历每一个数，然后从这个数的前一个数开始遍历，依次比较第一个比它还小的数。复杂度O(n^2)。那么如何优化这个过程呢？我们知道依次遍历是必须的，所以要从第二层循环开始优化，想一下，我们在第二层遍历的时候多算了什么？可以用什么优化？因为每次遍历的时候都会遍历一遍前面的数(很多已经多次遍历了)，如优化呢？可以将已经遍历完的数用栈存储，要用的时候在栈里面找，但是这样每次遍历一个就入栈一个和上面的算法无异处。我们可以用单调栈来存储，用单调栈就会删除一些元素，那么这样真的可以吗？仔细想一下遍历到第x个数，我们一定会去前面找第一个比arr[x]小的数，这样可以，但是我们要删除x前面比x大的数，这样会对后面产生影响吗？显然不会，因为x后面的数都要找“趋向于小”的数，那x不是比前面比x大的数小？前面的数也用不到啊。因此可以直接用单调栈来处理，每次遍历一个数，将这个数入栈并保持栈的单调性。
#include<iostream>
using namespace std;
const int N = 1e6+10;
int arr[N],q[N],hh,tt=-1;
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
for(int i=0;i<n;i++){
if(hh<=tt && i-k+1 >q[hh]) hh++;
while(hh<=tt && arr[q[tt]] >= arr[i]) tt--;
q[++tt] = i;
if(i-k+1>=0) printf("%d ",arr[q[hh]]);
}
printf("\n");
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt && i-k+1 >q[hh]) hh++;
while(hh<=tt && arr[q[tt]] <= arr[i]) tt--;
q[++tt] = i;
if(i-k+1>=0) printf("%d ",arr[q[hh]]);
}
return 0;
}思路：如果暴力的话要遍历每一个数，还要遍历这个数这个区间，第一层遍历是必须的，第二层遍历如何优化呢？假如一个窗口3个数，当遍历到第x个数时(假如前后都已经都超过3个数的位置)。我们之前的窗口要更新，把第x-3个数出队列(在队列中不一定是在队头！)。然后将第x个数入队，想一下，如果把第x-1的位置给占了，会有影响吗？其实是不会的，因为x-1个数的位置是在第x之前的(如果占掉了，就说明第x-1个数一定大于第x个数)当遍历到第x+1个数时，要么第x+1个数比第x个大，要么比x个数小，与x-1个数没有什么关系。然后找这个队列中最小的数，因为是递增的，所以一定是栈头。
原文地址：https://blog.csdn.net/2303_77275067/article/details/140722073
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！