【算法基础篇】数组模拟队列、滑动窗口问题

两种写法

数组模拟栈：

1. tt=-1, q[++tt]=x, hh<=tt 表示队列非空
2. tt=0, q[tt++]=x, hh<tt 表示队列非空

AC代码

#include <iostream>

using namespace std;

const int N = 100010;;
int queue[N], hh = 0, tt = 0;
int m;

int main()
&#123;
    cin >> m;
    while (m -- )
    &#123;
        string op;
        int x;
        cin >> op;
        if(op == "push")
        &#123;
            cin >> x;
            queue[tt] = x;
            tt ++;
        &#125;
        else if(op == "pop")
        &#123;
            hh ++;
        &#125;
        else if(op == "query")
        &#123;
            cout << queue[hh] << endl;
        &#125;
        else
        &#123;
            if(hh < tt) cout << "NO" <<endl;
            else cout << "YES" <<endl;
        &#125;

    &#125;
    return 0;
&#125;

习题 滑动窗口

题目

https://www.acwing.com/problem/content/156/

思路

https://www.acwing.com/solution/content/6564/
最小值和最大值分开来做，两个for循环完全类似，都做以下四步：

1. 解决队首已经出窗口的问题;
2. 解决队尾与当前元素a[i]不满足单调性的问题;
3. 将当前元素下标加入队尾;
4. 如果满足条件则输出结果;

AC代码

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], hh = 0, tt = -1;
int n, k;
int a[N];

int main()
&#123;
    cin >> n >> k;
    for (int i = 0; i < n; i ++) cin >> a[i];

    // 最小值
    for (int i = 0; i < n; i ++)
    &#123;
        // 维护窗口
        while (hh <= tt && i - q[hh] + 1 > k) hh ++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt --;

        q[++ tt] = i;
        if(i + 1 >= k) cout << a[q[hh]] << " ";    
    &#125;

    cout << endl;

    // 最大值
    hh = 0, tt = -1;
    for(int i = 0; i < n; i ++)
    &#123;
        // 维护滑动窗口大小
        while (hh <= tt && i - q[hh] + 1 > k) hh ++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt --;

        q[++ tt] = i;
        if(i + 1 >= k) cout << a[q[hh]] << " ";
    &#125;

    return 0;
&#125;