单调队列结构解决滑动窗口问题
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 239. Sliding Window Maximum | 239. 滑动窗口最大值 | 🔴 |
| - | 剑指 Offer 59 - I. 滑动窗口的最大值 | 🔴 |
| - | 剑指 Offer 59 - II. 队列的最大值 | 🟠 |
———–
前文用 单调栈解决三道算法问题 介绍了单调栈这种特殊数据结构，本文写一个类似的数据结构「单调队列」。
也许这种数据结构的名字你没听过，其实没啥难的，就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素全都是单调递增（或递减）的。
为啥要发明「单调队列」这种结构呢，主要是为了解决下面这个场景：
给你一个数组 window，已知其最值为 A，如果给 window 中添加一个数 B，那么比较一下 A 和 B 就可以立即算出新的最值；但如果要从 window 数组中减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是 A，就需要遍历 window 中的所有元素重新寻找新的最值。
这个场景很常见，但不用单调队列似乎也可以，比如优先级队列也是一种特殊的队列，专门用来动态寻找最值的，我创建一个大（小）顶堆，不就可以很快拿到最大（小）值了吗？
如果单纯地维护最值的话，优先级队列很专业，队头元素就是最值。但优先级队列无法满足标准队列结构「先进先出」的时间顺序，因为优先级队列底层利用二叉堆对元素进行动态排序，元素的出队顺序是元素的大小顺序，和入队的先后顺序完全没有关系。
所以，现在需要一种新的队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值，这就是「单调队列」结构。
「单调队列」这个数据结构主要用来辅助解决滑动窗口相关的问题，前文 滑动窗口核心框架 把滑动窗口算法作为双指针技巧的一部分进行了讲解，但有些稍微复杂的滑动窗口问题不能只靠两个指针来解决，需要上更先进的数据结构。
比方说，你注意看前文
滑动窗口核心框架 讲的几道题目，每当窗口扩大（right++）和窗口缩小（left++）时，你单凭移出和移入窗口的元素即可决定是否更新答案。
但就本文开头说的那个判断一个窗口中最值的例子，你就无法单凭移出窗口的那个元素更新窗口的最值，除非重新遍历所有元素，但这样的话时间复杂度就上来了，这是我们不希望看到的。
我们来看看力扣第 239 题「 滑动窗口最大值」，就是一道标准的滑动窗口问题：
给你输入一个数组 nums 和一个正整数 k，有一个大小为 k 的窗口在 nums 上从左至右滑动，请你输出每次窗口中 k 个元素的最大值。
函数签名如下：
int[] maxSlidingWindow(int[] nums, int k);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> maxSlidingWindow(vector<int>& nums, int k);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func maxSlidingWindow(nums []int, k int) []int
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var maxSlidingWindow = function(nums, k){
// function body here
}
比如说力扣给出的一个示例：
接下来，我们就借助单调队列结构，用 O(1) 时间算出每个滑动窗口中的最大值，使得整个算法在线性时间完成。
一、搭建解题框架
在介绍「单调队列」这种数据结构的 API 之前，先来看看一个普通的队列的标准 API：
class Queue {
// enqueue 操作，在队尾加入元素 n
void push(int n);
// dequeue 操作，删除队头元素
void pop();
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Queue {
public:
// enqueue 操作，在队尾加入元素 n
void push(int n);
// dequeue 操作，删除队头元素
void pop();
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Queue:
# enqueue 操作，在队尾加入元素 n
def push(self, n: int):
pass
# dequeue 操作，删除队头元素
def pop(self):
pass
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type Queue struct{}
// push 操作，在队尾加入元素 n
func (q *Queue) push(n int) {}
// pop 操作，删除队头元素
func (q *Queue) pop() {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var Queue = function() {
// enqueue 操作，在队尾加入元素 n
this.push = function (n) {
};
// dequeue 操作，删除队头元素
this.pop = function () {
};
};
我们要实现的「单调队列」的 API 也差不多：
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class MonotonicQueue {
public:
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class MonotonicQueue:
# 在队尾添加元素 n
def push(self, n: int):
pass
# 返回当前队列中的最大值
def max(self) -> int:
pass
# 队头元素如果是 n，删除它
def pop(self, n: int):
pass
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type MonotonicQueue struct {}
// 在队尾添加元素 n
func (q *MonotonicQueue) push(n int) {}
// 返回当前队列中的最大值
func (q *MonotonicQueue) max() int {
return 0
}
// 队头元素如果是 n，删除它
func (q *MonotonicQueue) pop(n int) {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var MonotonicQueue = function() {
// 在队尾添加元素 n
this.push = function(n) {
};
// 返回当前队列中的最大值
this.max = function() {
};
// 队头元素如果是 n，删除它
this.pop = function(n) {
};
}
当然，这几个 API 的实现方法肯定跟一般的 Queue 不一样，不过我们暂且不管，而且认为这几个操作的时间复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭出来：
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;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window; //Assuming MonotonicQueue class exists in C++
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;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from collections import deque
from typing import List
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
# 定义双端队列
window = deque()
# 定义结果列表
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 res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func maxSlidingWindow(nums []int, k int) []int {
window := NewMonotonicQueue()
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
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
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]);
}
}
// 将 List 类型转化成 int[] 数组作为返回值
var arr = new Array(res.length);
for (var i = 0; i < res.length; i++) {
arr[i] = res[i];
}
return arr;
};
这个思路很简单，能理解吧？下面我们开始重头戏，单调队列的实现。
二、实现单调队列数据结构
观察滑动窗口的过程就能发现，实现「单调队列」必须使用一种数据结构支持在头部和尾部进行插入和删除，很明显双链表是满足这个条件的。
「单调队列」的核心思路和「单调栈」类似，push 方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉：
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);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
#include<deque>
using namespace std;
class MonotonicQueue {
// 双链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
private:
deque<int> maxq;
// 在尾部添加一个元素 n，维护 maxq 的单调性质
public:
void push(int n) {
// 将前面小于自己的元素都删除
while (!maxq.empty() && maxq.back() < n) {
maxq.pop_back();
}
maxq.push_back(n);
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
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)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type MonotonicQueue struct {
// 双链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
maxq []int
}
// 在尾部添加一个元素 n，维护 mq 的单调性质
func (mq *MonotonicQueue) Push(n int) {
// 将前面小于自己的元素都删除
for len(mq.maxq) > 0 && mq.maxq[len(mq.maxq)-1] < n {
mq.maxq = mq.maxq[:len(mq.maxq)-1]
}
mq.maxq = append(mq.maxq, n)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var MonotonicQueue = function() {
// 双链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
this.maxq = [];
// 在尾部添加一个元素 n，维护 maxq 的单调性质
this.push = function(n) {
// 将前面小于自己的元素都删除
while (this.maxq.length && this.maxq[this.maxq.length - 1] < n) {
this.maxq.pop();
}
this.maxq.push(n);
}
}
你可以想象，加入数字的大小代表人的体重，体重大的会把前面体重不足的压扁，直到遇到更大的量级才停住。
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的 max 方法可以可以这样写：
class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
public int max() {
// 队头的元素肯定是最大的
return maxq.getFirst();
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
public:
int max() {
// 队头的元素肯定是最大的
return maxq.front();
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class MonotonicQueue:
# To save space, the previous code section is omitted...
def max(self) -> int:
# The first element of the queue is definitely the largest
return self.maxq[0] # 队头的元素肯定是最大的
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type MonotonicQueue struct {
// ...省略上文的代码部分
maxq []int // 记录最大值的队列
}
func (mq *MonotonicQueue) max() int {
// 队头的元素肯定是最大的
return mq.maxq[0]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var MonotonicQueue = function(){
// 为了节约篇幅，省略上文给出的代码部分...
this.max = function() {
// 队头的元素肯定是最大的
return maxq[0];
}
};
pop 方法在队头删除元素 n，也很好写：
class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
public void pop(int n) {
if (n == maxq.getFirst()) {
maxq.pollFirst();
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class MonotonicQueue {
// 为了节约篇幅，省略上文给出的代码部分...
public:
void pop(int n) {
if (n == maxq.front()) {
maxq.pop_front();
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class MonotonicQueue:
# To save space, the code given above is omitted here...
def pop(self, n: int) -> None:
if n == self.maxq[0]: # 如果当前最大值被弹出，则弹出队首元素
self.maxq.pop(0)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type MonotonicQueue struct {
//省略上文给出的代码部分
}
func (mq *MonotonicQueue) pop(n int) {
if n == mq.maxq[0] {
mq.maxq = mq.maxq[1:]
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var MonotonicQueue = function() {
// 为了节约篇幅，省略上文给出的代码部分...
this.pop = function(n) {
if (n == maxq.getFirst()) {
maxq.pollFirst();
}
}
}
之所以要判断 n == maxq.getFirst()，是因为我们想删除的队头元素 n 可能已经被「压扁」了，可能已经不存在了，所以这时候就不用删除了：
至此，单调队列设计完毕，看下完整的解题代码：
/* 单调队列的实现 */
class MonotonicQueue {
LinkedList<Integer> maxq = new LinkedList<>();
public void push(int n) {
// 将小于 n 的元素全部删除
while (!maxq.isEmpty() && maxq.getLast() < n) {/**<extend down -250><img src="/algo/images/单调队列/3.png"> */
maxq.pollLast();
}
// 然后将 n 加入尾部
maxq.addLast(n);
}
public int max() {
return maxq.getFirst();
}
public void pop(int n) {
if (n == maxq.getFirst()) {
maxq.pollFirst();
}
}
}
/* 解题函数的实现 */
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 {/**<extend up -100><img src="/algo/images/单调队列/1.png"> */
// 窗口向前滑动，加入新数字
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;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
/* 单调队列的实现 */
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();
}
}
};
/* 解题函数的实现 */
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;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class MonotonicQueue:
def __init__(self):
self.maxq = []
def push(self, n):
# 将小于 n 的元素全部删除
while self.maxq and self.maxq[-1] < n: # <extend up -100><img src="/algo/images/单调队列/3.png"> #
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)
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.push(nums[i])
else: # <extend up -100><img src="/algo/images/单调队列/1.png"> #
# 窗口向前滑动，加入新数字
window.push(nums[i])
# 记录当前窗口的最大值
res.append(window.max())
# 移出旧数字
window.pop(nums[i - k + 1])
return res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type MonotonicQueue struct {
maxq []int
}
func (mq *MonotonicQueue) push(n int) {
// 将小于 n 的元素全部删除
for len(mq.maxq) > 0 && mq.maxq[len(mq.maxq)-1] < n {
/* <extend down -250>
<figure><img src="/images/%e5%8d%95%e8%b0%83%e9%98%9f%e5%88%97/3.png"
class="shadow myimage"/>
</figure>
*/
mq.maxq = mq.maxq[:len(mq.maxq)-1]
}
// 然后将 n 加入尾部
mq.maxq = append(mq.maxq, n)
}
func (mq *MonotonicQueue) max() int {
return mq.maxq[0]
}
func (mq *MonotonicQueue) pop(n int) {
if n == mq.maxq[0] {
mq.maxq = mq.maxq[1:]
}
}
func maxSlidingWindow(nums []int, k int) []int {
window := MonotonicQueue{maxq: []int{}}
res := []int{}
for i := 0; i < len(nums); i++ {
if i < k-1 {
//先填满窗口的前 k - 1
window.push(nums[i])
} else {
/* <extend up -100>
<figure><img src="/images/%e5%8d%95%e8%b0%83%e9%98%9f%e5%88%97/1.png"
class="shadow myimage"/>
</figure>
*/
// 窗口向前滑动，加入新数字
window.push(nums[i])
// 记录当前窗口的最大值
res = append(res, window.max())
// 移出旧数字
window.pop(nums[i-k+1])
}
}
return res
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/* 单调队列的实现 */
function MonotonicQueue() {
this.maxq = [];
this.push = function(n) {
// 将小于 n 的元素全部删除
while (this.maxq.length > 0 && this.maxq[this.maxq.length - 1] < n) {/**<extend down -250><img src="/algo/images/单调队列/3.png"> */
this.maxq.pop();
}
// 然后将 n 加入尾部
this.maxq.push(n);
}
this.max = function() {
return this.maxq[0];
}
this.pop = function(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 {/**<extend up -100><img src="/algo/images/单调队列/1.png"> */
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.push(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
return res;
}
有一点细节问题不要忽略，在实现 MonotonicQueue 时，我们使用了 Java 的 LinkedList，因为链表结构支持在头部和尾部快速增删元素；而在解法代码中的 res 则使用的 ArrayList 结构，因为后续会按照索引取元素，所以数组结构更合适。
关于单调队列 API 的时间复杂度，读者可能有疑惑：push 操作中含有 while 循环，时间复杂度应该不是 O(1) 呀，那么本算法的时间复杂度应该不是线性时间吧？
这里就用到了 算法时空复杂度分析使用手册 中讲到的摊还分析：
单独看 push 操作的复杂度确实不是 O(1)，但是算法整体的复杂度依然是 O(N) 线性时间。要这样想，nums 中的每个元素最多被 push 和 pop 一次，没有任何多余操作，所以整体的复杂度还是 O(N)。空间复杂度就很简单了，就是窗口的大小 O(k)。
拓展延伸
最后，我提出几个问题请大家思考：
1、本文给出的 MonotonicQueue 类只实现了 max 方法，你是否能够再额外添加一个 min 方法，在 O(1) 的时间返回队列中所有元素的最小值？
2、本文给出的 MonotonicQueue 类的 pop 方法还需要接收一个参数，这显然有悖于标准队列的做法，请你修复这个缺陷。
3、请你实现 MonotonicQueue 类的 size 方法，返回单调队列中元素的个数（注意，由于每次 push 方法都可能从底层的 q 列表中删除元素，所以 q 中的元素个数并不是单调队列的元素个数）。
也就是说，你是否能够实现单调队列的通用实现：
/* 单调队列的通用实现，可以高效维护最大值和最小值 */
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();
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/* 单调队列的通用实现，可以高效维护最大值和最小值 */
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();
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 单调队列的通用实现，可以高效维护最大值和最小值
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
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// MonotonicQueue 单调队列的通用实现，可以高效维护最大值和最小值
type MonotonicQueue struct{}
// 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 {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/* 单调队列的通用实现，可以高效维护最大值和最小值 */
function MonotonicQueue() {
// 标准队列 API，向队尾加入元素
this.push = function(elem) {};
// 标准队列 API，从队头弹出元素，符合先进先出的顺序
this.pop = function() {};
// 标准队列 API，返回队列中的元素个数
this.size = function() {};
// 单调队列特有 API，O(1) 时间计算队列中元素的最大值
this.max = function() {};
// 单调队列特有 API，O(1) 时间计算队列中元素的最小值
this.min = function() {};
}
我将在 单调队列通用实现及应用 中给出单调队列的通用实现和经典习题。更多数据结构设计类题目参见 数据结构设计经典习题。
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
引用本文的文章
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释