滑动窗口最大值

难度：⭐⭐⭐⭐ Hard

考点

• 单调队列（双端队列）
• 滑动窗口 + 单调性维护
• 字节面试高频 Hard 题

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组最左侧移动到最右侧。你只能看到窗口内的 k 个数字。每次窗口向右移动一位，返回每个窗口位置的最大值。

函数签名

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

示例

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
窗口位置                最大值
[1  3  -1] -3  5  3  6  7      3
 1 [3  -1  -3] 5  3  6  7      3
 1  3 [-1  -3  5] 3  6  7      5
 1  3  -1 [-3  5  3] 6  7      5
 1  3  -1  -3 [5  3  6] 7      6
 1  3  -1  -3  5 [3  6  7]     7
输出：[3,3,5,5,6,7]

要求

1. 时间复杂度 O(n)（暴力 O(nk) 不可接受）
2. 使用单调递减队列

提示

• 单调队列（deque）存储索引，保持队列内元素对应的值单调递减
• 新元素入队前，移除队尾所有比它小的（它们不可能成为后续窗口的最大值）
• 队首超出窗口范围时弹出
• 每次队首就是当前窗口的最大值

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 || k == 0 {
		return nil
	}
	deque := make([]int, 0)   // 存索引，单调递减队列
	result := make([]int, 0, len(nums)-k+1)

	for i := 0; i < len(nums); i++ {
		// 移除超出窗口范围的队首
		for len(deque) > 0 && deque[0] <= i-k {
			deque = deque[1:]
		}
		// 维护单调递减：移除队尾所有比当前值小的
		for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
			deque = deque[:len(deque)-1]
		}
		deque = append(deque, i)
		// 窗口形成后收集结果
		if i >= k-1 {
			result = append(result, nums[deque[0]])
		}
	}
	return result
}