单调队列结构解决滑动窗口问题

labuladong原创数据结构单调队列约 2783 字大约 9 分钟

Info

新版网站会员open in new window 限时优惠；算法可视化编辑器上线，点击体验open in new window！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
239. Sliding Window Maximumopen in new window	239. 滑动窗口最大值open in new window	🔴
-	剑指 Offer 59 - I. 滑动窗口的最大值open in new window	🔴
-	剑指 Offer 59 - II. 队列的最大值open in new window	🟠

前文用单调栈解决三道算法问题介绍了单调栈这种特殊数据结构，本文写一个类似的数据结构「单调队列」。

也许这种数据结构的名字你没听过，其实没啥难的，就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素全都是单调递增（或递减）的。

为啥要发明「单调队列」这种结构呢，主要是为了解决下面这个场景：

给你一个数组 window，已知其最值为 A，如果给 window 中添加一个数 B，那么比较一下 A 和 B 就可以立即算出新的最值；但如果要从 window 数组中减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是 A，就需要遍历 window 中的所有元素重新寻找新的最值。

这个场景很常见，但不用单调队列似乎也可以，比如优先级队列也是一种特殊的队列，专门用来动态寻找最值的，我创建一个大（小）顶堆，不就可以很快拿到最大（小）值了吗？

如果单纯地维护最值的话，优先级队列很专业，队头元素就是最值。但优先级队列无法满足标准队列结构「先进先出」的时间顺序，因为优先级队列底层利用二叉堆对元素进行动态排序，元素的出队顺序是元素的大小顺序，和入队的先后顺序完全没有关系。

所以，现在需要一种新的队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值，这就是「单调队列」结构。

「单调队列」这个数据结构主要用来辅助解决滑动窗口相关的问题，前文滑动窗口核心框架把滑动窗口算法作为双指针技巧的一部分进行了讲解，但有些稍微复杂的滑动窗口问题不能只靠两个指针来解决，需要上更先进的数据结构。

比方说，你注意看前文滑动窗口核心框架讲的几道题目，每当窗口扩大（right++）和窗口缩小（left++）时，你单凭移出和移入窗口的元素即可决定是否更新答案。

但本文开头说的那个判断一个窗口中最值的例子，你无法单凭移出窗口的那个元素更新窗口的最值，除非重新遍历所有元素，但这样的话时间复杂度就上来了，这是我们不希望看到的。

我们来看看力扣第 239 题「滑动窗口最大值open in new window」，就是一道标准的滑动窗口问题：

给你输入一个数组 nums 和一个正整数 k，有一个大小为 k 的窗口在 nums 上从左至右滑动，请你输出每次窗口中 k 个元素的最大值。

函数签名如下：

java 🟢

int[] maxSlidingWindow(int[] nums, int k);

cpp 🤖

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

vector<int> maxSlidingWindow(vector<int>& nums, int k);

python 🤖

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:

go 🤖

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func maxSlidingWindow(nums []int, k int) []int

javascript 🤖

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var maxSlidingWindow = function(nums, k){
  // function body here 
}

比如说力扣给出的一个示例：

接下来，我们就借助单调队列结构，用 O(1) 时间算出每个滑动窗口中的最大值，使得整个算法在线性时间完成。

一、搭建解题框架

在介绍「单调队列」这种数据结构的 API 之前，先来看看一个普通的队列的标准 API：

java 🟢

class Queue {
    // enqueue 操作，在队尾加入元素 n
    void push(int n);
    // dequeue 操作，删除队头元素
    void pop();
}

cpp 🤖

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Queue {
public:
    // enqueue 操作，在队尾加入元素 n
    void push(int n);
    // dequeue 操作，删除队头元素
    void pop();
};

python 🤖

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Queue:
    # enqueue 操作，在队尾加入元素 n
    def push(self, n: int):
        pass
    
    # dequeue 操作，删除队头元素
    def pop(self):
        pass

go 🤖

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type Queue struct{}

// push 操作，在队尾加入元素 n
func (q *Queue) push(n int) {}

// pop 操作，删除队头元素
func (q *Queue) pop() {}

javascript 🤖

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var Queue = function() {
  // enqueue 操作，在队尾加入元素 n
  this.push = function (n) {

  };
  // dequeue 操作，删除队头元素
  this.pop = function () {

  };
};

我们要实现的「单调队列」的 API 也差不多：

java 🟢

class MonotonicQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n，删除它
    void pop(int n);
}

cpp 🤖

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class MonotonicQueue {
public:
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n，删除它
    void pop(int n);
};

python 🤖

# 注意：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 🤖

// 注意：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 🤖

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var MonotonicQueue = function() {
  // 在队尾添加元素 n
  this.push = function(n) {

  };
  // 返回当前队列中的最大值
  this.max = function() {

  };
  // 队头元素如果是 n，删除它
  this.pop = function(n) {

  };
}

当然，这几个 API 的实现方法肯定跟一般的 Queue 不一样，不过我们暂且不管，而且认为这几个操作的时间复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭出来：

java 🟢

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 🤖

// 注意：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 🤖

# 注意：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 🤖

// 注意：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 🤖

// 注意：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 方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉：

java 🟢

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 🤖

// 注意：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 🤖

# 注意：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 🤖

// 注意：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 🤖

// 注意：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 方法可以可以这样写：

java 🟢

class MonotonicQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

    public int max() {
        // 队头的元素肯定是最大的
        return maxq.getFirst();
    }
}

cpp 🤖

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class MonotonicQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

    public:
    int max() {
        // 队头的元素肯定是最大的
        return maxq.front();
    }
};

python 🤖

# 注意：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 🤖

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type MonotonicQueue struct {
    // ...省略上文的代码部分

    maxq []int // 记录最大值的队列
}

func (mq *MonotonicQueue) max() int {
    // 队头的元素肯定是最大的
    return mq.maxq[0]
}

javascript 🤖

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var MonotonicQueue = function(){
    // 为了节约篇幅，省略上文给出的代码部分...

    this.max = function() {
        // 队头的元素肯定是最大的
        return maxq[0];
    }
};

pop 方法在队头删除元素 n，也很好写：

java 🟢

class MonotonicQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

    public void pop(int n) {
        if (n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

cpp 🤖

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class MonotonicQueue {
    // 为了节约篇幅，省略上文给出的代码部分...

    public:
        void pop(int n) {
            if (n == maxq.front()) {
                maxq.pop_front();
            }
        }
};

python 🤖

# 注意：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 🤖

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type MonotonicQueue struct {
	//省略上文给出的代码部分
}

func (mq *MonotonicQueue) pop(n int) {
	if n == mq.maxq[0] {
		mq.maxq = mq.maxq[1:]
	}
}

javascript 🤖

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var MonotonicQueue = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

    this.pop = function(n) {
        if (n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

之所以要判断 n == maxq.getFirst()，是因为我们想删除的队头元素 n 可能已经被「压扁」了，可能已经不存在了，所以这时候就不用删除了：

至此，单调队列设计完毕，看下完整的解题代码：

java 🟢

/* 单调队列的实现 */
class MonotonicQueue {
    LinkedList<Integer> maxq = new LinkedList<>();
    public void push(int n) {
        // 将小于 n 的元素全部删除
        while (!maxq.isEmpty() && maxq.getLast() < n) {/**<extend down -250><div class="img-content"><img src="/algo/images/单调队列/3.png" class="myimage"/></div> */
            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><div class="img-content"><img src="/algo/images/单调队列/1.png" class="myimage"/></div> */
            // 窗口向前滑动，加入新数字
            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 🤖

// 注意：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 🤖

# 注意：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><div class="img-content"><img src="/algo/images/单调队列/3.png" class="myimage"/></div> #
            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><div class="img-content"><img src="/algo/images/单调队列/1.png" class="myimage"/></div> #
            # 窗口向前滑动，加入新数字
            window.push(nums[i])
            # 记录当前窗口的最大值
            res.append(window.max())
            # 移出旧数字
            window.pop(nums[i - k + 1])
    return res

go 🤖

// 注意：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>
        <div class="img-content"><img src="/images/单调队列/3.png" class="myimage"/></div>
        */
        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>
            <div class="img-content"><img src="/images/单调队列/1.png" class="myimage"/></div>
            */
            // 窗口向前滑动，加入新数字
            window.push(nums[i])
            // 记录当前窗口的最大值
            res = append(res, window.max())
            // 移出旧数字
            window.pop(nums[i-k+1])
        }
    }
    return res
}

javascript 🤖

// 注意：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><div class="img-content"><img src="/algo/images/单调队列/3.png" class="myimage"/></div> */
            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><div class="img-content"><img src="/algo/images/单调队列/1.png" class="myimage"/></div> */
            // 窗口向前滑动，加入新数字
            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 中的元素个数并不是单调队列的元素个数）。

也就是说，你是否能够实现单调队列的通用实现：

java 🟢

/* 单调队列的通用实现，可以高效维护最大值和最小值 */
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 🤖

// 注意：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 🤖

# 注意：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 🤖

// 注意：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 🤖

// 注意：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 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
1425. Constrained Subsequence Sumopen in new window	1425. 带限制的子序列和open in new window
1696. Jump Game VIopen in new window	1696. 跳跃游戏 VIopen in new window
862. Shortest Subarray with Sum at Least Kopen in new window	862. 和至少为 K 的最短子数组open in new window
918. Maximum Sum Circular Subarrayopen in new window	918. 环形子数组的最大和open in new window
-	剑指 Offer 59 - I. 滑动窗口的最大值open in new window

《labuladong 的算法笔记》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：