单调队列，即单调递减或单调递增的队列。而且，队首和队尾都可以进行出队操作，但只有队尾可以进行入队操作。它类似于下面这幅图：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
暴力方法，遍历一遍的过程中每次从窗口中在找到最大的数值,
对于长度为 nn 的数组 numsnums 而言，窗口的数量为 n−k+1n−k+1，因此该算法的时间复杂度为 O((n−k+1)k)=O(n * k)的算法。我们可以想到，对于两个相邻（只差了一个位置）的滑动窗口，它们共用着 k−1k−1 个元素，而只有 11 个元素是变化的。我们可以根据这个特点进行优化。
我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。那怎么知道最大值呢？
所以这里就要维护一个单调递减的队列，这样队头就是最大值。为了保证队头的值最大，后续入队列的元素都是比它小的，而且是依次单调递减的元素。可是一旦发现某个元素入队时，它居然比队头元素更大，此时队列的单调性就不能维持了，我们就要把原来入队的元素都干掉，只留下这个新来的元素，让单调队列一切重新开始。
这个过程有点封建王朝，人们不断的追求权力，但是不允许自己的后来者超过自己，可是皇位不可能永传，新来者会推翻一切，重新洗牌，循环往复。
代码
class Solution {
public:
// 求出滑动窗口的最大值
vector<int> maxSlidingWindow(vector<int> &nums, int k)
{
int n = nums.size();
// 为了可以同时弹出队首和队尾的元素，使用deque
// 使用一个单调队列，存储所有还没有被移除的下标，即窗口的大小，下标对应的值单调递增
deque<int> q;
for (int i = 0; i < k; ++i) { // 初始滑动窗口的处理
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = { nums[q.front()] }; // 存入前面K个元素中的最大值
for (int i = k; i < n; ++i) { // 当滑动窗口向右移动
while (!q.empty() && nums[i] >= nums[q.back()]) { // 新来的元素比对列中的大，则队列中的元素要被移除
q.pop_back();
}
q.push_back(i); // 后续的值入队列
while (q.front() <= i - k) { // 此时队头的元素就是队中所有元素的最大值，但是如果该值如果不在该窗口中
q.pop_front(); // 也要移除它
}
ans.push_back(nums[q.front()]); // 此时队首下标对应的元素就是滑动窗口中的最大值
}
return ans;
}
};
对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int> &nums, int k)
{
int n = nums.size();
// pair第一个元素代表值，第二个元素代表索引
priority_queue<pair<int, int>> q; // 最大堆
for (int i = 0; i < k; ++i) { // 我们将数组前 k 个元素放入优先队列中
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first}; // 最大值
for (int i = k; i < n; ++i) { // 当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中
q.emplace(make_pair(nums[i], i));
while (q.top().second <= i - k) { // 此时堆顶的元素就是堆中所有元素的最大值，但是该值如果不在该窗口中
q.pop(); // 移除它
}
ans.push_back(q.top().first);
}
return ans;
}
};
参考：