宣传：算法主页

$\Huge 单调栈$

$问题描述$

给定长度为 $n$ 的序列 $a$ 。

对于每一个 $a_i$ ，求在它前面第一个大于它的数。

$过程$

从左往右扫描序列 $a$ ，对于每一个 $a_i$ ：

• 若栈顶元素 $a_{top} \leq a_i$ 则在之后的答案中不可能出现 $a_{top}$ ，将栈顶元素弹出。
• 反复执行步骤1 ，最后栈中元素单调递减。
• 答案一定为栈中某个元素， $a_{top}$ 为第一个大于 $a_i$ 的数，第一个大于它的数是 $a_{top}$ 。
• 加入元素 $a_i$ 。

时间复杂度为 $O(n)$

$实现$

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
int w[N], q[N];

int main()
{
    scanf("%d",&n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    w[0] = -1;
    int tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (tt && w[q[tt]] >= w[i])tt -- ;
        printf("%d ", w[q[tt]]);
        q[++ tt] = i;
    }

    return 0;
}

$\Huge 单调队列$

$题目描述$

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。

现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

$过程$

以最大值为例。

队列开头为 $hh$ ，结尾为 $tt$ ，对于每一个 $a_i$ ：

• 若 $i - hh + 1\ge k$ ，则弹出队头元素。
• 若 $a_{tt} \leq a_i$ ，则在之后的询问中不可能出现 $a_{tt}$ ，弹出队尾元素（循环此步骤多次）。
• 加入元素 $a_i$ ，队列保持单调递减。
• $hh$ 位置上的元素在队列中最大，以 $i$ 结尾的最大值为 $a_{hh}$

时间复杂度 $O(n)$

$实现$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N], q[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
    {
        if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
        while (hh <= tt && a[q[tt]] > a[i]) tt -- ;
        q[ ++ tt] = i;
        if(i >= k) printf("%d ", a[q[hh]]); 
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
    {
        if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
        while (hh <= tt && a[q[tt]] < a[i]) tt -- ;
        q[ ++ tt] = i;
        if (i - k >= 0) printf("%d ", a[q[hh]]);
    }

    return 0;
}