---
title: "单调队列"
created: 2025-11-28
tags:
  - 算法
---

# 单调队列

## 题目 [滑动窗口](https://www.acwing.com/problem/content/156/)

![[image-27f04ffd.png]]

![[image-e96e20f6.png]]

## 思路分析

![[image-9646b6ad.png]]

![[image-a440095c.png]]

整理一下就是几个关键点

一个原本的数组a[] 一个单调队列维护答案q[] 对头为hh=0 队尾为tt=-1

单调队列中存放的是答案所在的**下标**

 \*\*\*\*

保证窗口始终不大于3

使用i-k+1（窗口的左端点）去与队头元素比较（队列里放的下标 所以能比较）

若i-k+1>q[hh]则说明原本队列里的队头元素不在窗口里了 要hh++

但是这样只能保证不大于3 为了防止不断hh++使得队列没了

还得加上条件hh<=tt

所以

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

`hh ++ ;`

第二点

因为队列里放的是下标

所以在对每个元素判断进而决定是否修改队列时 需要做的判断也要修改

如果新元素插入 会和队尾元素形成逆序 就tt--；

判断条件应该是a[q[tt]] 注意q里是下标 下标

同理 防止一直tt--导致队列没了 还得加上hh<=tt

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

`tt -- ;`

在对队列修改完后 要把当前元素入队

`q[ ++ tt] = i;`

这里也要注意 是入队下标！

第三点

什么时候有答案 答案是什么

窗口形成时才有答案 答案是对头元素

窗口形成怎么判断？ 窗口大小为3 那就i在第三位置的时候呗

`if (i >= k - 1)`

`printf("%d ", a[q[hh]]);`

如果要求窗口最大值 也是同理

只要把这里的单调递增改成单调递减即可

要改的地方只有第二步 判断部分

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

`tt -- ;`

`q[ ++ tt] = i;`

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1000010;

int a[N],q[N];

int main()

{

    int n,k;

    cin>>n>>k;

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

        scanf("%d",&a[i]);

    int hh=0,tt=-1;//队尾插入 tt=-1 q[++tt]可以保证0号位置被用

    for(int i=0;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-1)

            printf("%d ",a[q[hh]]);

    }

    cout<<endl;

    //记得重置队列

    hh=0,tt=-1;

    for(int i=0;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-1)

            printf("%d ",a[q[hh]]);

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/02-听课板子/数据结构/栈与队列/单调栈|单调栈]] 🏠 [[00-听课板子]] ➡️ [[串|串]]