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

# 单调队列

- [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调队列/单调队列|单调队列]]

## 分析

滑动窗口并不对应单调队列

滑动窗口问题可以用双指针 和 队列 两种方式实现

单调队列只是针对这个窗口里的某个性质 将不必要的元素舍去

从而能在O(1)的时间内找到这个最值

一般也就两个场景

### 找窗口的最小值

```cpp
void get_min(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k)
            hh++;
        //求最小 递增区间 若出现向下 出队
        while(hh<=tt && a[i]<=a[q[tt]])
            tt--;
        q[++tt]=i;
        //当前区间的最大值为队头
        b[i] = a[q[hh]];
    }
}
```

### 找窗口的最大值

```cpp
void get_max(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k)
            hh++;
        //求最大 递减区间 若出现向上 出队
        while(hh<=tt && a[i]>=a[q[tt]])
            tt--;
        q[++tt]=i;
        //当前区间的最大值为队头
        b[i] = a[q[hh]];
    }
}
```

另外注意分析 我们要的答案是在插入新元素之前还是在插入新元素之后

```cpp
void get_max/* min */(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k) //这里一定有等于 因为要腾空间放新元素 满了就得出去
            hh++;

        //具体操作也可能放在这里
        //这是把新元素放进去之前就找答案

        //最大最小只要改这里 最大应该是递减 最小应该是递增 出现异常就出队
        //另外注意代入情景看等于是否影响结果 一般是也剔除 除非是要什么最左边的 才考虑去=
        while(hh<=tt && a[i]>/* < */=a[q[tt]])
            tt--;
        q[++tt]=i;

        //具体操作可能放在这里
        //这是把新元素放进去后再找答案
    }
}
```

stl版

```java
class Solution {
public:
    vector<int> maxInWindows/* minInWindows */(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i=0;i<nums.size();i++)
        {
            if(!q.empty() && i-q.front()>=k)
                q.pop_front();

            //具体操作 情况2
            //……

            while(!q.empty() && nums[i]>= /* <= */ nums[q.back()])
                q.pop_back();
            q.push_back(i);

            //具体操作 情况1
            //……
            if(i>=k-1)
                res.push_back(nums[q.front()]);
        }
        return res;
    }
};
```

## 题目

- [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调队列/单调队列|单调队列]]
- [[滑动窗口的最大值|滑动窗口的最大值]]

- [[最大子序和|最大子序和]]
- [[切蛋糕|切蛋糕]]

- [[子矩阵|子矩阵]]

更多题目：

- [剑指 Offer 59 - II. 队列的最大值](http://leetcode-cn.com/problems/sliding-window-maximum/)
- [滑动窗口最大值](http://leetcode-cn.com/problems/sliding-window-maximum/)
- [剑指 Offer 59 - I. 滑动窗口的最大值](http://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/)
- [绝对差不超过限制的最长连续子数组](http://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/)
- [跳跃游戏 VI](http://leetcode-cn.com/problems/jump-game-vi/)
- [带限制的子序列和](http://leetcode-cn.com/problems/constrained-subsequence-sum/)
- [环形子数组的最大和](https://leetcode-cn.com/problems/maximum-sum-circular-subarray/)
- [和至少为 K 的最短子数组](https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/)
- [分割数组的最大值](https://leetcode-cn.com/problems/split-array-largest-sum/)

---
⬅️ [[直方图中最大的矩形|直方图中最大的矩形]] 🏠 [[00-刷题理模型]] ➡️ [[切蛋糕|切蛋糕]]