单调队列结构解决滑动窗口问题
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 239. Sliding Window Maximum | 🔴 |
| 面试题59 - II. 队列的最大值 LCOF | 🟠 |
Prerequisites
Before reading this article, you should first learn:
In the previous article Solving Three Algorithm Problems with a Monotonic Stack, we introduced the special data structure called a monotonic stack. This article will discuss a similar data structure called the "monotonic queue."
You might not have heard of this data structure before, but it’s not difficult to understand. Essentially, it’s just a "queue" that uses a clever method to ensure that the elements in the queue are either monotonically increasing or decreasing.
Why was the "monotonic queue" invented? Mainly to solve the following scenario:
Given an array window with a known maximum value A, if you add a number B to window, you can immediately determine the new maximum by comparing A and B. However, if you remove a number from window, you can’t directly determine the new maximum. If the removed number happens to be A, you need to traverse all elements in window to find the new maximum.
This scenario is common, but it seems like you could handle it without a monotonic queue. For example, a priority queue is a special kind of queue designed to dynamically find the maximum (or minimum) value. By creating a max (or min) heap, you can quickly get the maximum (or minimum) value.
If you only need to maintain the maximum value, a priority queue is very effective; the front element is always the maximum. However, a priority queue cannot maintain the "first-in, first-out" time order of a standard queue. This is because a priority queue uses a binary heap to dynamically sort elements, so the dequeue order is based on element size, not the order in which they were added.
Therefore, we need a new queue structure that can maintain the "first-in, first-out" time order of elements and correctly maintain the maximum value of all elements in the queue. This is where the "monotonic queue" comes in.
The "monotonic queue" data structure is mainly used to help solve problems related to sliding windows. In the previous article Core Framework of Sliding Window, we discussed the sliding window algorithm as part of the two-pointer technique. However, some more complex sliding window problems require more advanced data structures.
For example, in the previous article Core Framework of Sliding Window, the problems discussed allow you to update the answer based on the elements entering and leaving the window whenever the window expands (right++) or contracts (left++).
However, in the example at the beginning of this article about determining the maximum value in a window, you can't update the maximum value based solely on the element leaving the window. You would need to traverse all elements again, which increases the time complexity, something we want to avoid.
Let's look at LeetCode Problem 239 "Sliding Window Maximum," which is a standard sliding window problem:
Given an array nums and a positive integer k, there is a window of size k that slides from left to right over nums. Please output the maximum value of the k elements in the window each time the window slides.
The function signature is as follows:
int[] maxSlidingWindow(int[] nums, int k);vector<int> maxSlidingWindow(vector<int>& nums, int k);def maxSlidingWindow(nums: List[int], k: int) -> List[int]:func maxSlidingWindow(nums []int, k int) []intvar maxSlidingWindow = function(nums, k)比如说力扣给出的一个示例：
输入：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] 7Next, we will use a monotonic queue structure to compute the maximum value in each sliding window in O(1) time, allowing the entire algorithm to complete in linear time.
1. Building the Solution Framework
Before introducing the API of the "monotonic queue" data structure, let's first compare the standard API of a regular queue with the API implemented by a monotonic queue:
// 普通队列的 API
class Queue {
// enqueue 操作，在队尾加入元素 n
void push(int n);
// dequeue 操作，删除队头元素
void pop();
}
// 单调队列的 API
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}// 普通队列的 API
class Queue {
public:
// enqueue 操作，在队尾加入元素 n
void push(int n);
// dequeue 操作，删除队头元素
void pop();
};
// 单调队列的 API
class MonotonicQueue {
public:
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
};# 普通队列的 API
class Queue:
# enqueue 操作，在队尾加入元素 n
def push(self, n: int):
pass
# dequeue 操作，删除队头元素
def pop(self):
pass
# 单调队列的 API
class MonotonicQueue:
# 在队尾添加元素 n
def push(self, n: int):
pass
# 返回当前队列中的最大值
def max(self) -> int:
pass
# 队头元素如果是 n，删除它
def pop(self, n: int):
pass// 普通队列的 API
type Queue struct{}
// push 操作，在队尾加入元素 n
func (q *Queue) push(n int) {}
// pop 操作，删除队头元素
func (q *Queue) pop() {}
// 单调队列的 API
type MonotonicQueue struct{}
// 在队尾添加元素 n
func (q *MonotonicQueue) push(n int) {}
// 返回当前队列中的最大值
func (q *MonotonicQueue) max() int {}// 普通队列的 API
class Queue {
// enqueue 操作，在队尾加入元素 n
push(n) {}
// dequeue 操作，删除队头元素
pop() {}
};
// 单调队列的 API
class MonotonicQueue {
// 在队尾添加元素 n
push(n) {}
// 返回当前队列中的最大值
max() {}
// 队头元素如果是 n，删除它
pop(n) {}
};Of course, the implementation of these few APIs for a monotonic queue is definitely different from a regular Queue. But for now, let's not worry about that and assume that the time complexity for these operations is O(1). Let's first establish the framework for solving this "sliding window" problem:
int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
// 先把窗口的前 k - 1 填满
window.push(nums[i]);
} else {
// 窗口开始向前滑动
// 移入新元素
window.push(nums[i]);
// 将当前窗口中的最大元素记入结果
res.add(window.max());
// 移出最后的元素
window.pop(nums[i - k + 1]);
}
}
// 将 List 类型转化成 int[] 数组作为返回值
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}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;
}from collections import deque
from typing import List
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
window = MonotonicQueue()
res = []
for i in range(len(nums)):
if i < k - 1:
# 先将窗口前 k - 1 填满
window.append(nums[i])
else:
# 窗口开始向前滑动
# 移入新元素
window.append(nums[i])
# 将当前窗口中的最大元素记入结果
res.append(max(window))
# 移出最后的元素
window.popleft()
# 将 List 类型转化成 int[] 数组作为返回值
return resfunc maxSlidingWindow(nums []int, k int) []int {
window := MonotonicQueue{}
var res []int
for i:=0; i<len(nums); i++ {
if i < k - 1 {
// 先把窗口的前 k-1 填满
window.Push(nums[i])
} else {
// 窗口开始向前滑动
// 移入新元素
window.Push(nums[i])
// 将当前窗口中的最大元素记入结果
res = append(res, window.Max())
// 移出最后的元素
window.Pop(nums[i-k+1])
}
}
return res
}var maxSlidingWindow = function(nums, k) {
var window = new MonotonicQueue();
var res = [];
for (var i = 0; i < nums.length; i++) {
if (i < k - 1) {
// 先把窗口的前 k - 1 填满
window.push(nums[i]);
} else {
// 窗口开始向前滑动
// 移入新元素
window.push(nums[i]);
// 将当前窗口中的最大元素记入结果
res.push(window.max());
// 移出最后的元素
window.pop(nums[i - k + 1]);
}
}
return res;
};
This idea is simple, right? Now let's get to the main part, implementing the monotonic queue.
2. Implementing the Monotonic Queue Data Structure
By observing the sliding window process, you will find that to implement a "monotonic queue," we need a data structure that allows insertion and deletion at both the head and tail. Clearly, a doubly linked list meets this requirement.
The core idea of the "monotonic queue" is similar to the "monotonic stack." The push method still adds elements to the tail of the queue, but it removes all elements in front that are smaller than the new element:
class MonotonicQueue {
// 双链表，支持快速在头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
private LinkedList<Integer> maxq = new LinkedList<>();
// 在尾部添加一个元素 n，维护 maxq 的单调性质
public void push(int n) {
// 将前面小于自己的元素都删除
while (!maxq.isEmpty() && maxq.getLast() < n) {
maxq.pollLast();
}
maxq.addLast(n);
}
}#include <list>
using namespace std;
class MonotonicQueue {
// 双链表，支持快速在头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
list<int> maxq;
public:
// 在尾部添加一个元素 n，维护 maxq 的单调性质
void push(int n) {
// 将前面小于自己的元素都删除
while (!maxq.empty() && maxq.back() < n) {
maxq.pop_back();
}
maxq.push_back(n);
}
};from collections import deque
class MonotonicQueue:
def __init__(self):
# 使用双端队列，支持头部和尾部增删元素
# 维护其中的元素自尾部到头部单调递增
self.maxq = deque()
# 在尾部添加一个元素 n，维护 maxq 的单调性质
def push(self, n: int) -> None:
# 将前面小于自己的元素都删除
while len(self.maxq) > 0 and self.maxq[-1] < n:
self.maxq.pop()
self.maxq.append(n)import (
"container/list"
)
type MonotonicQueue struct {
// 使用 golang 双链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
maxq list.List
}
// 在尾部添加一个元素 n，维护 mq 的单调性质
func (mq *MonotonicQueue) Push(n int) {
// 将前面小于自己的元素都删除
for mq.maxq.Len() > 0 && mq.maxq.Back().Value.(int) < n {
mq.maxq.Remove(mq.maxq.Back())
}
}class MonotonicQueue {
constructor() {
// JS 没有内置支持快速增删头尾元素的数据结构
// 暂时用普通数组代替吧，不过这样在头部删除元素时性能会差一些
// 维护其中的元素自尾部到头部单调递增
this.maxq = []
}
// 在尾部添加一个元素 n，维护 maxq 的单调性质
push(n) {
// 将前面小于自己的元素都删除
while (this.maxq.length > 0 && this.maxq[this.maxq.length - 1] < n) {
this.maxq.pop()
}
this.maxq.push(n)
}
}Imagine that the size of the numbers represents people's weights. Heavier weights will push down the lighter weights in front of them until they encounter a heavier weight.
If every element is added in this manner, the elements in the monotonic queue will eventually maintain a monotonically decreasing order. Thus, our max method becomes straightforward: simply return the front element of the queue. The pop method also operates on the front of the queue. If the front element is the element n to be removed, then we delete it:
class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
public int max() {
// 队头的元素肯定是最大的
return maxq.getFirst();
}
public void pop(int n) {
if (n == maxq.getFirst()) {
maxq.pollFirst();
}
}
}class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
public:
int max() {
// 队头的元素肯定是最大的
return maxq.front();
}
void pop(int n) {
if (n == maxq.front()) {
maxq.pop_front();
}
}
};class MonotonicQueue:
# 为了节约篇幅，省略上文给出的代码部分...
def max(self) -> int:
# 队头的元素肯定是最大的
return self.maxq[0]
def pop(self, n: int) -> None:
if n == self.maxq[0]:
self.maxq.popleft()// 为了节约篇幅，省略上文给出的代码部分...
func (mq *MonotonicQueue) max() int {
// 队头的元素肯定是最大的
return mq.maxq.Front().Value.(int)
}
func (mq *MonotonicQueue) pop(n int) {
if n == mq.maxq.Front().Value.(int) {
mq.maxq.Remove(mq.maxq.Front())
}
}class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
max() {
// 队头的元素肯定是最大的
return this.maxq[0];
}
pop(n) {
if (n === this.maxq[0]) {
this.maxq.shift();
}
}
}The reason the pop method checks n == maxq.getFirst() is that the front element n we want to remove might have already been "flattened" during the push process and may no longer exist. In this case, there is no need to delete it:
At this point, the design of the monotonic queue is complete. Let's look at the complete solution code:
// 单调队列的实现
class MonotonicQueue {
LinkedList<Integer> maxq = new LinkedList<>();
public void push(int n) {
// 将小于 n 的元素全部删除
while (!maxq.isEmpty() && maxq.getLast() < n) {
maxq.pollLast();
}
// 然后将 n 加入尾部
maxq.addLast(n);
}
public int max() {
return maxq.getFirst();
}
public void pop(int n) {
if (n == maxq.getFirst()) {
maxq.pollFirst();
}
}
}
class Solution {
int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
// 先填满窗口的前 k - 1
window.push(nums[i]);
} else {
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.add(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
// 需要转成 int[] 数组再返回
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
}// 单调队列的实现
class MonotonicQueue {
deque<int> maxq;
public:
void push(int n) {
// 将小于 n 的元素全部删除
while (!maxq.empty() && maxq.back() < n) {
maxq.pop_back();
}
// 然后将 n 加入尾部
maxq.push_back(n);
}
int max() {
return maxq.front();
}
void pop(int n) {
if (n == maxq.front()) {
maxq.pop_front();
}
}
};
class Solution {
public:
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;
}
};class MonotonicQueue:
def __init__(self):
self.maxq = []
def push(self, n):
# 将小于 n 的元素全部删除
while self.maxq and self.maxq[-1] < n:
self.maxq.pop()
# 然后将 n 加入尾部
self.maxq.append(n)
def max(self):
return self.maxq[0]
def pop(self, n):
if n == self.maxq[0]:
self.maxq.pop(0)
class Solution(object):
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
window = MonotonicQueue()
res = []
for i in range(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 resimport (
"container/list"
)
type MonotonicQueue struct {
maxq list.List
}
func (mq *MonotonicQueue) push(n int) {
// 将小于 n 的元素全部删除
for mq.maxq.Len() > 0 && mq.maxq.Back().Value.(int) < n {
mq.maxq.Remove(mq.maxq.Back())
}
// 然后将 n 加入尾部
mq.maxq.PushBack(n)
}
func (mq *MonotonicQueue) max() int {
return mq.maxq.Front().Value.(int)
}
func (mq *MonotonicQueue) pop(n int) {
if n == mq.maxq.Front().Value.(int) {
mq.maxq.Remove(mq.maxq.Front())
}
}
func maxSlidingWindow(nums []int, k int) []int {
window := MonotonicQueue{maxq: list.List{}}
res := []int{}
for i := 0; i < len(nums); i++ {
if i < k-1 {
// 先填满窗口的前 k - 1
window.push(nums[i])
} else {
/* <extend up -100>
<div class="img-content"><img src="/images/单调队列/1.png" alt class="myimage" loading="lazy" photo-swipe="" /></div>
*/
// 窗口向前滑动，加入新数字
window.push(nums[i])
// 记录当前窗口的最大值
res = append(res, window.max())
// 移出旧数字
window.pop(nums[i-k+1])
}
}
return res
}// 单调队列的实现
class MonotonicQueue {
constructor() {
this.maxq = [];
}
push(n) {
// 将小于 n 的元素全部删除
while (this.maxq.length > 0 && this.maxq[this.maxq.length - 1] < n) {
this.maxq.pop();
}
// 然后将 n 加入尾部
this.maxq.push(n);
}
max() {
return this.maxq[0];
}
pop(n) {
if (n === this.maxq[0]) {
this.maxq.shift();
}
}
}
function maxSlidingWindow(nums, k) {
var window = new MonotonicQueue();
var res = [];
for (var i = 0; i < nums.length; i++) {
if (i < k - 1) {
// 先填满窗口的前 k - 1
window.push(nums[i]);
} else {
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.push(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
return res;
}There is a small detail that should not be overlooked. When implementing MonotonicQueue, we used Java's LinkedList because the linked list structure allows for quick insertion and deletion of elements at both the head and the tail. In contrast, the res in the solution code uses an ArrayList because we need to access elements by index later on, making the array structure more suitable. Implementations in other languages should also pay attention to these details.
Regarding the time complexity of the Monotonic Queue API, readers might wonder: the push operation contains a while loop, so the time complexity shouldn't be O(1), right? Therefore, the overall time complexity of this algorithm shouldn't be linear time, correct?
This is where the amortized analysis from the Guide to Algorithm Time and Space Complexity Analysis comes into play:
Individually, the complexity of the push operation is indeed not O(1), but the overall complexity of the algorithm is still O(N) linear time. Think of it this way: each element in nums is pushed and popped at most once, with no redundant operations, so the overall complexity is still O(N). The space complexity is straightforward, which is the size of the window O(k).
Further Extension
Finally, I propose a few questions for everyone to think about:
The
MonotonicQueueclass provided in this article only implements themaxmethod. Can you add aminmethod that returns the minimum value of all elements in the queue inO(1)time?The
popmethod of theMonotonicQueueclass currently requires an argument, which is not elegant and deviates from the standard queue API. Can you fix this issue?Implement the
sizemethod for theMonotonicQueueclass to return the number of elements in the monotonic queue. (Note: Since thepushmethod may remove elements from the underlyingqlist, the number of elements inqis not the same as the number of elements in the monotonic queue.)
In other words, can you implement a general-purpose monotonic queue?
// 单调队列的通用实现，可以高效维护最大值和最小值
class MonotonicQueue<E extends Comparable<E>> {
// 标准队列 API，向队尾加入元素
public void push(E elem);
// 标准队列 API，从队头弹出元素，符合先进先出的顺序
public E pop();
// 标准队列 API，返回队列中的元素个数
public int size();
// 单调队列特有 API，O(1) 时间计算队列中元素的最大值
public E max();
// 单调队列特有 API，O(1) 时间计算队列中元素的最小值
public E min();
}// 单调队列的通用实现，可以高效维护最大值和最小值
template <typename E>
class MonotonicQueue {
public:
// 标准队列 API，向队尾加入元素
void push(E elem);
// 标准队列 API，从队头弹出元素，符合先进先出的顺序
E pop();
// 标准队列 API，返回队列中的元素个数
int size();
// 单调队列特有 API，O(1) 时间计算队列中元素的最大值
E max();
// 单调队列特有 API，O(1) 时间计算队列中元素的最小值
E min();
};# 单调队列的通用实现，可以高效维护最大值和最小值
class MonotonicQueue:
def push(self, elem: 'Comparable') -> None:
pass
# 标准队列 API，从队头弹出元素，符合先进先出的顺序
def pop(self) -> 'Comparable':
pass
# 标准队列 API，返回队列中的元素个数
def size(self) -> int:
pass
# 单调队列特有 API，O(1) 时间计算队列中元素的最大值
def max(self) -> 'Comparable':
pass
# 单调队列特有 API，O(1) 时间计算队列中元素的最小值
def min(self) -> 'Comparable':
pass// MonotonicQueue 单调队列的通用实现，可以高效维护最大值和最小值
type MonotonicQueue struct{}
type Comparable interface {
// 比较函数，返回值为 -1, 0, 1 分别代表小于、等于、大于
compare(Comparable) int
}
// push 向队尾加入元素
func (q *MonotonicQueue) push(elem Comparable) {}
// pop 从队头弹出元素，符合先进先出的顺序
func (q *MonotonicQueue) pop() Comparable {}
// size 返回队列中的元素个数
func (q *MonotonicQueue) size() int {}
// max 单调队列特有 API，O(1) 时间计算队列中元素的最大值
func (q *MonotonicQueue) max() Comparable {}
// min 单调队列特有 API，O(1) 时间计算队列中元素的最小值
func (q *MonotonicQueue) min() Comparable {}// 单调队列的通用实现，可以高效维护最大值和最小值
class MonotonicQueue {
// 标准队列 API，向队尾加入元素
push(elem) {}
// 标准队列 API，从队头弹出元素，符合先进先出的顺序
pop() {}
// 标准队列 API，返回队列中的元素个数
size() {}
// 单调队列特有 API，O(1) 时间计算队列中元素的最大值
max() {}
// 单调队列特有 API，O(1) 时间计算队列中元素的最小值
min() {}
}I will provide a generic implementation and classic exercises for monotonic queues in Generic Implementation and Applications of Monotonic Queues. For more data structure design problems, refer to Classic Exercises on Data Structure Design.
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
