# 特殊数据结构:单调队列
![](../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======其他语言代码====== ### python3 由[SCUHZS](ttps://github.com/brucecat)提供 ```python from collections import deque class MonotonicQueue(object): def __init__(self): # 双端队列 self.data = deque() def push(self, n): # 实现单调队列的push方法 while self.data and self.data[-1] < n: self.data.pop() self.data.append(n) def max(self): # 取得单调队列中的最大值 return self.data[0] def pop(self, n): # 实现单调队列的pop方法 if self.data and self.data[0] == n: self.data.popleft() class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: # 单调队列实现的窗口 window = MonotonicQueue() # 结果 res = [] for i in range(0, len(nums)): if i < k-1: # 先填满窗口前k-1 window.push(nums[i]) else: # 窗口向前滑动 window.push(nums[i]) res.append(window.max()) window.pop(nums[i-k+1]) return res ``` ### java ```java class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len = nums.length; // 判断数组或者窗口长度为0的情况 if (len * k == 0) { return new int[0]; } /* 采用两端扫描的方法 将数组分成大小为 k 的若干个窗口, 对每个窗口分别从左往右和从右往左扫描, 记录扫描的最大值 left[] 记录从左往右扫描的最大值 right[] 记录从右往左扫描的最大值 */ int[] left = new int[len]; int[] right = new int[len]; for (int i = 0; i < len; i = i + k) { // 每个窗口中的第一个值 left[i] = nums[i]; // 窗口的最后边界 int index = i + k - 1 >= len ? len - 1 : i + k - 1; // 每个窗口的最后一个值 right[index] = nums[index]; // 对该窗口从左往右扫描 for (int j = i + 1; j <= index; j++) { left[j] = Math.max(left[j - 1], nums[j]); } // 对该窗口从右往左扫描 for (int j = index - 1; j >= i; j--) { right[j] = Math.max(right[j + 1], nums[j]); } } int[] arr = new int[len - k + 1]; // 对于第 i 个位置, 它一定是该窗口从右往左扫描数组中的最后一个值, 相对的 i + k - 1 是该窗口从左向右扫描数组中的最后一个位置 // 对两者取最大值即可 for (int i = 0; i < len - k + 1; i++) { arr[i] = Math.max(right[i], left[i + k - 1]); } return arr; } } ```