手写队列解决滑动窗口

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

const int N = 1e7 + 10, M = 500;

int a[N], q[M];

int n, k;

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++)

    {

        while (hh <= tt && i - k + 1 > q[hh])

            hh++;

        while (hh <= tt && a[i] < a[q[tt]])

            tt--;

        q[++tt] = i;

        if (i >= k - 1)

            cout << a[q[hh]] << " ";

    }

    puts(" ");

    hh = 0, tt = -1;

    for (int i = 0; i < n; i++)

    {

        while (hh <= tt && i - k + 1 > q[hh])

            hh++;

        while (hh <= tt && a[i] > a[q[tt]])

            tt--;

        q[++tt] = i;

        if (i >= k - 1)

            cout << a[q[hh]] << " ";

    }

}