# 特殊数据结构:单调队列
![](../pictures/souyisou.png) 相关推荐: * [几个反直觉的概率问题](https://labuladong.gitbook.io/algo) * [Git/SQL/正则表达式的在线练习平台](https://labuladong.gitbook.io/algo) 读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目: [239.滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum) **-----------** 前文讲了一种特殊的数据结构「单调栈」monotonic stack,解决了一类问题「Next Greater Number」,本文写一个类似的数据结构「单调队列」。 也许这种数据结构的名字你没听过,其实没啥难的,就是一个「队列」,只是使用了一点巧妙的方法,使得队列中的元素单调递增(或递减)。这个数据结构有什么用?可以解决滑动窗口的一系列问题。 看一道 LeetCode 题目,难度 hard: ![](../pictures/单调队列/title.png) ### 一、搭建解题框架 这道题不复杂,难点在于如何在 O(1) 时间算出每个「窗口」中的最大值,使得整个算法在线性时间完成。在之前我们探讨过类似的场景,得到一个结论: 在一堆数字中,已知最值,如果给这堆数添加一个数,那么比较一下就可以很快算出最值;但如果减少一个数,就不一定能很快得到最值了,而要遍历所有数重新找最值。 回到这道题的场景,每个窗口前进的时候,要添加一个数同时减少一个数,所以想在 O(1) 的时间得出新的最值,就需要「单调队列」这种特殊的数据结构来辅助了。 一个普通的队列一定有这两个操作: ```java class Queue { void push(int n); // 或 enqueue,在队尾加入元素 n void pop(); // 或 dequeue,删除队头元素 } ``` 一个「单调队列」的操作也差不多: ```java class MonotonicQueue { // 在队尾添加元素 n void push(int n); // 返回当前队列中的最大值 int max(); // 队头元素如果是 n,删除它 void pop(int n); } ``` 当然,这几个 API 的实现方法肯定跟一般的 Queue 不一样,不过我们暂且不管,而且认为这几个操作的时间复杂度都是 O(1),先把这道「滑动窗口」问题的解答框架搭出来: ```cpp vector======其他语言代码======