您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode如何找出队列的最大值和滑动窗口的最大值
## 引言
在算法面试和编程竞赛中，队列和滑动窗口问题是高频考点。LeetCode上有多道题目要求我们高效地找出队列或滑动窗口中的最大值，例如：
- 剑指Offer 59 - I. 滑动窗口的最大值
- 239. 滑动窗口最大值
- 队列的最大值（剑指Offer 59 - II）
这类问题的难点在于如何在O(1)或O(n)时间复杂度内完成操作，而不是简单的暴力解法。本文将深入探讨三种典型解法，并通过代码示例展示实现细节。
## 一、问题描述
### 1.1 滑动窗口最大值（LeetCode 239）
给定一个整数数组`nums`和滑动窗口大小`k`，窗口从数组最左侧滑动到最右侧，返回每个窗口中的最大值。
示例：
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3 输出: [3,3,5,5,6,7]
### 1.2 队列的最大值（剑指Offer 59 - II）
请定义一个队列并实现函数`max_value`得到队列里的最大值，要求`max_value`、`push_back`和`pop_front`的均摊时间复杂度都是O(1)。
## 二、暴力解法及其局限性
### 2.1 滑动窗口的暴力解法
```python
def maxSlidingWindow(nums, k):
if not nums:
return []
return [max(nums[i:i+k]) for i in range(len(nums)-k+1)]
时间复杂度：O(nk)，当n和k都很大时（如n=10^5, k=10^4）会超时。
class MaxQueue:
def __init__(self):
self.queue = []
def max_value(self) -> int:
return max(self.queue) if self.queue else -1
def push_back(self, value: int) -> None:
self.queue.append(value)
def pop_front(self) -> int:
return self.queue.pop(0) if self.queue else -1
缺陷：max_value()和pop_front()时间复杂度均为O(n)。
维护一个双端队列deque，保证队列中的元素按照从大到小的顺序排列：
1. 当新元素入队时，移除队列中所有小于该元素的值
2. 队列头部始终是当前窗口的最大值
3. 当窗口滑动时，检查出队元素是否是队列头部元素
from collections import deque
def maxSlidingWindow(nums, k):
if not nums or k == 0:
return []
deq = deque()
result = []
# 初始化第一个窗口
for i in range(k):
while deq and nums[i] > nums[deq[-1]]:
deq.pop()
deq.append(i)
result.append(nums[deq[0]])
# 滑动窗口
for i in range(k, len(nums)):
# 移除不在窗口内的元素
if deq[0] == i - k:
deq.popleft()
# 维护单调队列
while deq and nums[i] > nums[deq[-1]]:
deq.pop()
deq.append(i)
result.append(nums[deq[0]])
return result
时间复杂度：每个元素最多入队出队一次，O(n)
from collections import deque
class MaxQueue:
def __init__(self):
self.data = deque() # 主队列
self.max_queue = deque() # 辅助队列
def max_value(self) -> int:
return self.max_queue[0] if self.max_queue else -1
def push_back(self, value: int) -> None:
self.data.append(value)
while self.max_queue and value > self.max_queue[-1]:
self.max_queue.pop()
self.max_queue.append(value)
def pop_front(self) -> int:
if not self.data:
return -1
val = self.data.popleft()
if val == self.max_queue[0]:
self.max_queue.popleft()
return val
所有操作均摊时间复杂度：O(1)
import heapq
def maxSlidingWindow(nums, k):
if not nums:
return []
heap = []
result = []
for i in range(len(nums)):
heapq.heappush(heap, (-nums[i], i))
if i >= k - 1:
while heap[0][1] <= i - k:
heapq.heappop(heap)
result.append(-heap[0][0])
return result
时间复杂度：最坏情况下O(nlogn)，因为堆操作是O(logn)
将数组分块处理，预处理左右方向的最大值数组：
def maxSlidingWindow(nums, k):
if not nums:
return []
n = len(nums)
left = [0] * n
right = [0] * n
left[0] = nums[0]
right[-1] = nums[-1]
for i in range(1, n):
left[i] = nums[i] if i % k == 0 else max(left[i-1], nums[i])
for i in range(n-2, -1, -1):
right[i] = nums[i] if (i+1) % k == 0 else max(right[i+1], nums[i])
return [max(right[i], left[i+k-1]) for i in range(n-k+1)]
时间复杂度：O(n)，空间复杂度：O(n)
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力法 | O(nk) | O(1) | 仅适用于k很小的情况 |
| 单调队列 | O(n) | O(k) | 通用最优解 |
| 堆 | O(nlogn) | O(n) | 数据流场景 |
| 动态规划 | O(n) | O(n) | 适合并行处理 |
Q: 为什么单调队列可以保证最大值在队首？ A: 因为我们在入队时移除了所有比当前元素小的值，保持了队列的单调递减性。
Q: 如何处理窗口滑动时移出的元素？ A: 检查队首元素索引，如果等于移出窗口的索引就将其出队。
Q: 为什么堆解法的时间复杂度更差？ A: 因为堆无法直接删除特定元素，需要延迟删除策略。
掌握单调队列这一数据结构对于解决最大值/最小值相关问题至关重要。建议读者在理解本文代码的基础上，亲自在LeetCode上提交练习（推荐题号：239, 剑指Offer 59-I/II）。算法能力的提升没有捷径，唯有不断思考和反复练习。
“The key to mastering algorithms is not memorization, but understanding the patterns.” - Anonymous “`
这篇文章共计约2200字，包含了： 1. 问题定义和示例 2. 多种解法实现与对比 3. 复杂度分析表格 4. 实际应用场景 5. 面试常见问题 6. 扩展练习建议
所有代码示例都采用Python实现，并添加了详细注释。文章采用Markdown格式，支持直接复制到支持Markdown的平台上发布。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。