队列与单调队列基础原理与题目说明

队列与单调队列基础原理与题目说明文章目录队列与单调队列基础原理与题目说明一、 队列Queue与双端队列Deque核心机制1.1 基础概念1.2 核心操作与优势二、 核心对比单调队列 vs 单调栈三、 单调队列实战演练[239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/) 查看完整专栏LeetCode基础算法专栏点击阅读Python 数据结构与语法速查笔记点击阅读哈希表基础原理与题目说明点击阅读双指针基础原理与题目说明点击阅读滑动窗口基础原理与题目说明点击阅读队列与单调队列基础原理与题目说明点击阅读二分查找基础原理与题目说明点击阅读矩阵基础原理与题目说明特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。一、 队列Queue与双端队列Deque核心机制1.1 基础概念普通队列Queue遵循先进先出FIFO, First In First Out原则的线性数据结构。常用于广度优先搜索BFS、任务调度等场景。双端队列Deque允许在两端队首和队尾同时进行插入和删除操作的高阶结构。在 Python 中通常使用collections.deque实现。1.2 核心操作与优势在 Python 中双端队列的左右两端操作时间复杂度均为O ( 1 ) O(1)O(1)入队append(x)尾部插入 /appendleft(x)头部插入出队pop()尾部弹出 /popleft()头部弹出算法优势双端队列能够高效地维护一个区间窗口的元素集合。因为可以同时从队首和队尾进行动态调整它成为了解决滑动窗口极值问题的绝佳容器。二、 核心对比单调队列 vs 单调栈在算法实战中单调队列与单调栈常常容易混淆。单调队列本质上是基于双端队列实现的用于维护区间内元素的单调性递增或递减。两者的核心区别如下特性维度单调队列Monotonic Queue单调栈Monotonic Stack访问范围可在队首和队尾两端操作仅能在栈顶一端操作典型用途滑动窗口极值如窗口最大/最小值全局次序问题如寻找下一个更大元素、括号匹配维护规律队列中元素严格单调递减或递增栈中元素单调递增或递减动态维护可以随窗口滑动从队首主动删除过期元素属于全局累加问题通常不涉及因“过期”而强制弹出三、 单调队列实战演练单调队列最经典的实战场景即是“滑动窗口最大值”它将暴力解法的O ( n ⋅ k ) O(n \cdot k)O(n⋅k)复杂度完美优化到了O ( n ) O(n)O(n)。239. 滑动窗口最大值题目描述给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。请返回滑动窗口中的最大值列表。解题思路使用双端队列deque维护一个单调递减的队列队列中存储的是数组的索引而非具体值方便判断元素是否滑出窗口。队首永远维护当前窗口内最大值的索引。队尾当新元素准备入队时将队列中所有对应值小于当前新元素的索引全部弹出因为当前新元素不仅更大且生命周期更长前面的小元素永无出头之日。状态流转模拟单调队列以数组[1, 3, -1, -3, 5, 3, 6, 7]k3为例窗口状态队列内索引队列对应元素状态流转解释[1, 3, -1][1, 2][3, -1]入队3时因3 1将1的索引弹出1不可能成为后续最大值[3, -1, -3][1, 2, 3][3, -1, -3]入队-3因-3 -1符合单调递减保留队列长度为 3[-1, -3, 5][4][5]入队5因5大于队尾对应值队尾全部弹出最后只保留5[-3, 5, 3][4, 5][5, 3]入队3因3 5符合递减保留入队[5, 3, 6][6][6]入队6因6大于前面的值队尾全部弹出[3, 6, 7][7][7]入队7因7 6队尾弹出此时队首为7核心代码fromtypingimportListfromcollectionsimportdequeclassSolution:defmaxSlidingWindow(self,nums:List[int],k:int)-List[int]:# 1. 创建双端队列用于存储元素的索引deqdeque()ans[]# 2. 遍历数组动态维护单调队列fori,numinenumerate(nums):# [Process] 维护单调性若队尾对应的元素小于当前元素则弹出队尾# 因为当前元素更大且更晚过期被弹出的元素绝对不可能成为最大值whiledeqandnums[deq[-1]]num:deq.pop()# [Process] 将当前元素的索引加入队尾deq.append(i)# [Process] 维护窗口边界若队首的索引已经滑出当前窗口(i-k)则弹出队首ifdeq[0]i-k:deq.popleft()# [Process] 记录答案当窗口形成后索引 i k-1队首即为当前窗口最大值ifik-1:ans.append(nums[deq[0]])returnans复杂度分析时间复杂度O ( n ) O(n)O(n)。虽然for循环内嵌套了while循环但每个元素的索引最多入队一次、出队一次总体操作次数不超过2 n 2n2n。空间复杂度O ( k ) O(k)O(k)。单调队列中最多存储k kk个元素的索引。