共计 2637 个字符，预计需要花费 7 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
239. 滑动窗口最大值
———–
前文讲了一种非凡的数据结构「枯燥栈」monotonic stack，解决了一类问题「Next Greater Number」，本文写一个相似的数据结构「枯燥队列」。
兴许这种数据结构的名字你没听过，其实没啥难的，就是一个「队列」，只是应用了一点奇妙的办法，使得队列中的元素枯燥递增（或递加）。这个数据结构有什么用？能够解决滑动窗口的一系列问题。
看一道 LeetCode 题目，难度 hard：
一、搭建解题框架
这道题不简单，难点在于如何在 O(1) 工夫算出每个「窗口」中的最大值，使得整个算法在线性工夫实现。在之前咱们探讨过相似的场景，失去一个论断：
在一堆数字中，已知最值，如果给这堆数增加一个数，那么比拟一下就能够很快算出最值；但如果缩小一个数，就不肯定能很快失去最值了，而要遍历所有数从新找最值。
回到这道题的场景，每个窗口后退的时候，要增加一个数同时缩小一个数，所以想在 O(1) 的工夫得出新的最值，就须要「枯燥队列」这种非凡的数据结构来辅助了。
一个一般的队列肯定有这两个操作：
class Queue {void push(int n);
// 或 enqueue，在队尾退出元素 n
void pop();
// 或 dequeue，删除队头元素
}一个「枯燥队列」的操作也差不多：
class MonotonicQueue {
// 在队尾增加元素 n
void push(int n);
// 返回以后队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}当然，这几个 API 的实现办法必定跟个别的 Queue 不一样，不过咱们暂且不论，而且认为这几个操作的工夫复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭进去：
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {if (i < k - 1) { // 先把窗口的前 k - 1 填满
window.push(nums[i]);
} else { // 窗口开始向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k + 1]);
// nums[i - k + 1] 就是窗口最初的元素
}
}
return res;
}
这个思路很简略，能了解吧？上面咱们开始重头戏，枯燥队列的实现。
二、实现枯燥队列数据结构
首先咱们要意识另一种数据结构：deque，即双端队列。很简略：
class deque {
// 在队头插入元素 n
void push_front(int n);
// 在队尾插入元素 n
void push_back(int n);
// 在队头删除元素
void pop_front();
// 在队尾删除元素
void pop_back();
// 返回队头元素
int front();
// 返回队尾元素
int back();}而且，这些操作的复杂度都是 O(1)。这其实不是啥稀奇的数据结构，用链表作为底层构造的话，很容易实现这些性能。
「枯燥队列」的外围思路和「枯燥栈」相似。枯燥队列的 push 办法仍然在队尾增加元素，然而要把后面比新元素小的元素都删掉：
class MonotonicQueue {
private:
deque<int> data;
public:
void push(int n) {while (!data.empty() && data.back() < n)
data.pop_back();
data.push_back(n);
}
};你能够设想，退出数字的大小代表人的体重，把后面体重有余的都压扁了，直到遇到更大的量级才停住。
如果每个元素被退出时都这样操作，最终枯燥队列中的元素大小就会放弃一个枯燥递加的程序，因而咱们的 max() API 能够能够这样写：
int max() {return data.front();
}pop() API 在队头删除元素 n，也很好写：
void pop(int n) {if (!data.empty() && data.front() == n)
data.pop_front();} 之所以要判断 data.front() == n，是因为咱们想删除的队头元素 n 可能曾经被「压扁」了，这时候就不必删除了：
至此，枯燥队列设计结束，看下残缺的解题代码：
class MonotonicQueue {
private:
deque<int> data;
public:
void push(int n) {while (!data.empty() && data.back() < n)
data.pop_back();
data.push_back(n);
}
int max() { return data.front(); }
void pop(int n) {if (!data.empty() && data.front() == n)
data.pop_front();}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {if (i < k - 1) { // 先填满窗口的前 k - 1
window.push(nums[i]);
} else { // 窗口向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k + 1]);
}
}
return res;
}三、算法复杂度剖析
读者可能纳闷，push 操作中含有 while 循环，工夫复杂度不是 O(1) 呀，那么本算法的工夫复杂度应该不是线性工夫吧？
独自看 push 操作的复杂度的确不是 O(1)，然而算法整体的复杂度仍然是 O(N) 线性工夫。要这样想，nums 中的每个元素最多被 push_back 和 pop_back 一次，没有任何多余操作，所以整体的复杂度还是 O(N)。
空间复杂度就很简略了，就是窗口的大小 O(k)。
四、最初总结
有的读者可能感觉「枯燥队列」和「优先级队列」比拟像，实际上差异很大的。
枯燥队列在增加元素的时候靠删除元素放弃队列的枯燥性，相当于抽取出某个函数中枯燥递增（或递加）的局部；而优先级队列（二叉堆）相当于主动排序，差异大了去了。
连忙去拿下 LeetCode 第 239 道题吧～