目录
一、单调队列介绍
单调队列是一种特殊的队列数据结构，它能够在常数时间内找到队列中的最值。单调队列可以用来解决一些与最值相关的问题，例如滑动窗口最大值、滑动窗口最小值（即由于维护一个输入序列中指定区间的最值）。
单调队列的主要操作有两个：添加元素和移除元素。添加元素时，我们需要保持队列的单调性，即保证在添加新元素后，队列仍然是递增（或递减）的。为了实现这一点，我们可以将新元素与队尾元素进行比较，如果新元素大于（或小于）队尾元素，则将队尾元素移除，直到队列保持单调性为止。移除元素时，我们只需要判断队首元素是否需要移除即可。
值得说明的是，单调队列并非是成型的stl，一般通过双端队列（deque）来实现，双端队列具有队列和栈的性质，可以在队首和队尾进行插入和删除操作。通过双端队列，我们可以在常数时间内完成单调队列的添加和移除操作。
下面来看一个例子。
二、题目应用
1.题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
2.解题碎碎念
单调队列的一个核心思路是只保留有可能成为最大值的元素，已经明确不可能成为最大值的元素直接pop出去不再考虑（这一点是和优先队列的显著区别，具体看下面的扩展）。
先形成第一个窗口，找出第一个最大值。
接着依次将后面的元素入队，凡是单调队列中小于要入队元素的，统统pop出去，直到遇到一个大于等于要入队元素的时停止pop，将要入队元素入队。
同时每次移动窗口时还要出队一个元素，如果要出队元素对于当前单调队列的最大值，则说明接下来的窗口最大值要改变，将单调队列左端元素出队。
3.代码示例
vector<int> maxSlidingWindow(vector<int>& nums, int k){
vector<int>ans; //ans作为返回结果
deque<int>win; //win是双端队列，用于构造单调队列
for (int i = 0; i < k; i++) //将第一个窗口中的最大值放入win、ans中
{
while (!win.empty() && nums[i] > win.back())
win.pop_back();
win.push_back(nums[i]);
}
ans.push_back(win.front());
//滑动窗口还是离不开双指针
for (int start = 1, end = k; end < nums.size(); start++, end++)
{
if (win.front() == nums[start - 1])
win.pop_front();
while (!win.empty() && nums[end] > win.back())
win.pop_back();
win.push_back(nums[end]);
ans.push_back(win.front()); //win的最左端一定是最大值
}
return ans;
}
三、扩展
1.与优先队列区别
##在应用场景方面：
单调队列可以总结为：及时去掉无用数据，保证双端队列有序。即单调队列中并非有输入序 列的所有元素。
而优先队列并非如此，它可以保存输入序列的所有元素并保证输出的依次为最值，它只要求能够高效地找到队列中的最值。
##在实现方式方面也有所不同：
单调队列可以使用双端队列（deque）来实现，通过保持队列的单调性，可以在常数时间内找到队列的最值。
优先队列可以使用堆（heap）来实现，它是一种特殊的二叉树结构，可以在对数时间内找到队列的最值
2.单调队列其他题目
