动态滑动窗口最大值问题指的是给定一个整数数组和一个固定大小的窗口，窗口从数组左侧开始向右滑动，每次滑动一个位置，要求实时返回每个窗口内的最大值。如果使用暴力法，每个窗口都需要遍历k个元素找最大值，整体时间复杂度为O(nk)，效率较低。而使用单调队列可以在Θ(n)时间内完成求解，核心思路是维护一个存储元素下标的双端队列，保证队列对应元素的值从队首到队尾是递减的。
核心思路解析
单调队列的本质是一个双端队列，我们需要遵循两个核心操作规则：
- 当新元素进入队列时，从队尾开始比较，如果队尾对应的元素值小于等于当前新元素，就弹出队尾元素，直到队尾元素大于当前新元素或者队列为空，再将当前元素的下标加入队尾。这样可以保证队列内的元素值始终是递减的，队首就是当前窗口的最大值下标。
- 每次窗口滑动时，需要判断队首的下标是否已经不在当前窗口范围内，如果不在就弹出队首元素，保证队首对应的元素始终在当前窗口内。
每个元素最多只会进入队列一次，也最多只会弹出队列一次，因此整体的时间复杂度是Θ(n)，空间复杂度为O(k)，k是窗口的大小。
实现步骤
步骤1：初始化数据结构
创建一个双端队列，用来存储数组元素的下标，同时创建一个结果数组，用来存储每个窗口的最大值。
步骤2：遍历数组处理每个元素
对于数组中的每个元素，先执行队尾清理操作，再执行队首过期检查，最后将当前元素下标加入队列，当窗口形成后记录最大值。
步骤3：返回结果数组
遍历完成后，结果数组中就存储了所有滑动窗口的最大值，直接返回即可。
代码示例（Python实现）
from collections import deque
def max_sliding_window(nums, k):
# 处理边界情况
if not nums or k == 0:
return []
if k == 1:
return nums.copy()
# 双端队列，存储元素下标
deq = deque()
# 结果数组
res = []
for i in range(len(nums)):
# 队尾清理：如果队尾元素对应的值小于等于当前元素，弹出队尾
while deq and nums[deq[-1]] <= nums[i]:
deq.pop()
# 将当前元素下标加入队尾
deq.append(i)
# 队首过期检查：如果队首下标不在当前窗口范围内，弹出队首
# 当前窗口的左边界是i - k + 1，队首下标需要大于等于左边界
if deq[0] < i - k + 1:
deq.popleft()
# 当窗口形成时，记录最大值（队首元素对应的值）
if i >= k - 1:
res.append(nums[deq[0]])
return res
# 测试示例
if __name__ == "__main__":
test_nums = [1,3,-1,-3,5,3,6,7]
test_k = 3
print(max_sliding_window(test_nums, test_k)) # 输出[3,3,5,5,6,7]
代码示例（Java实现）
import java.util.ArrayDeque;
import java.util.Deque;
public class SlidingWindowMaximum {
public static int[] maxSlidingWindow(int[] nums, int k) {
// 处理边界情况
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
if (k == 1) {
return nums.clone();
}
// 双端队列，存储元素下标
Deque<Integer> deq = new ArrayDeque<>();
// 结果数组
int[] res = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
// 队尾清理：如果队尾元素对应的值小于等于当前元素，弹出队尾
while (!deq.isEmpty() && nums[deq.peekLast()] <= nums[i]) {
deq.pollLast();
}
// 将当前元素下标加入队尾
deq.offerLast(i);
// 队首过期检查：如果队首下标不在当前窗口范围内，弹出队首
if (deq.peekFirst() < i - k + 1) {
deq.pollFirst();
}
// 当窗口形成时，记录最大值（队首元素对应的值）
if (i >= k - 1) {
res[idx++] = nums[deq.peekFirst()];
}
}
return res;
}
public static void main(String[] args) {
int[] testNums = {1,3,-1,-3,5,3,6,7};
int k = 3;
int[] result = maxSlidingWindow(testNums, k);
for (int num : result) {
System.out.print(num + " ");
}
// 输出3 3 5 5 6 7
}
}
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | Θ(n)，每个元素最多进入和弹出队列各一次，遍历数组的总操作次数是线性的 |
| 空间复杂度 | O(k)，双端队列中最多存储k个元素的下标，k是滑动窗口的大小 |
常见问题说明
为什么队列中存储的是下标而不是元素值？因为我们需要判断队首元素是否已经滑出当前窗口，存储下标可以直接通过下标范围判断，比存储值更方便处理窗口滑动的边界问题。
如果数组中有重复的最大值怎么办？单调队列的规则是队尾元素值小于等于当前元素就弹出，因此重复的最大值会保留最新的下标，当旧的下标滑出窗口后，新的下标会成为队首，不影响最大值的正确性。
单调队列是解决滑动窗口类问题的通用思路，除了最大值问题，还可以用来求解滑动窗口最小值、滑动窗口内的第k大元素等类似问题，核心都是维护队列的单调性来减少不必要的比较操作。