1单调队列 算法原理

1. 单调队列是一种特殊的队列，它维护队列中的元素始终保持单调性（递增或递减）。在滑动窗口最大值问题中，我们使用单调递减队列：
2. 队列中存储的是元素的索引而非元素值本身（在可视化中，我们同时显示索引和对应的值）
3. 队列头部始终是当前窗口中的最大值索引
4. 当新元素进入窗口时，从队尾移除所有小于新元素的值（它们不可能成为未来窗口的最大值）
5. 当窗口滑动时，检查队首元素是否仍在窗口内，如果不在则将其移除

2滑动窗口

题目分析

单调队列模板题。

如果找滑动窗口最小值，当前元素如果比队列中已有元素都要小，那么这些元素都要出队，因为当前元素不仅更年轻、更符合要求，而且，生命周期更长。

参考程序

#include<bits/stdc++.h>
usingnamespacestd;


constint N = 1e6 + 10;


int n, k;
int a[N], q[N];


intmain(){


  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];


  int hh = 0, tt = -1;


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


  cout << endl;


  hh = 0, tt = -1;


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


  return0;
}

3扫描

题目分析

单调队列基础模板题，同上一题。

参考程序

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


const int N = 2e6 + 10;


int n, k;
int a[N];


int q[N], hh = 0, tt = -1;


int main() {


    cin >> n >> k;


    for(int i = 1; i <= n; i++) cin >> a[i];


    for(int i = 1; i <= n; i++){
        if(hh <= tt && i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if(i >= k)
            cout << a[q[hh]] << endl;
    }


  return0;
}

4质量检测

题目分析

单调队列基础模板题，同上一题。

参考程序

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


const int N = 1e5 + 10;


int n, k;
int a[N];


int q[N], hh = 0, tt = -1;


int main() {


    cin >> n >> k;


    for(int i = 1; i <= n; i++) cin >> a[i];


    for(int i = 1; i <= n; i++){
        if(hh <= tt && i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if(i >= k)
            cout << a[q[hh]] << endl;
    }


  return0;
}

4求m区间内的最小值

题目分析

单调递增队列 O(n)

维护结构

• 用一个队列存“下标”，并保持其对应值单调递增。
• 队头永远是窗口最小值的下标。
• 队列大小不固定，但下标始终在当前滑窗范围内。

参考程序

#include<bits/stdc++.h>
usingnamespacestd;


constint N = 2e6 + 10;
int n, m;
int a[N];
int q[N], hh = 0, tt = -1;   


intmain(){


    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];


    for (int i = 1; i <= n; ++i) {
        // 1) 弹掉已滑出窗口的元素 —— 只可能在队头
        while (hh <= tt && q[hh] < i - m) hh++;


        // 2) 输出答案（窗口里无元素则输出 0）
        if (hh <= tt) cout << a[q[hh]] << endl;
        else  cout << 0 << endl;


        // 3) 维护单调递增队列（最小值在前）
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;      // 把当前下标 i 插到队尾
    }
    return0;
}