题目描述#

咱来翻译下题面：给定一个整数数组 nums，再给一个窗口大小 k。这个窗口一开始覆盖数组最左边的 k 个元素，之后每次向右移动一位。

每次移动时，只能看到当前窗口里的 k 个数字，需要记录这个窗口中的最大值。最后返回所有窗口最大值组成的数组。

思路#

如果每个窗口都重新扫一遍最大值，时间复杂度会变成 O(nk)，困难题嘛，当然不会让咱这么轻松糊弄过去。关键是：窗口向右移动时，大部分元素其实还留在窗口里，没必要重复比较。

这里用一个单调递减队列来保存“仍然有机会成为窗口最大值”的下标。队首下标对应的元素，就是当前窗口里的最大值。队列里存下标而不是直接存值，是因为咱还要判断某个元素是不是已经滑出窗口左边界。

遍历到位置 i 时，先检查队首是否已经在窗口外，也就是 queue[0] <= i-k，如果是就把它弹掉。接着维护队列的单调性：只要队尾元素 nums[queue[len(queue)-1]] <= nums[i]，它以后就不可能再成为最大值了，因为当前元素不仅更大或相等，而且位置还更靠右，存活时间更久，所以可以直接弹出。

处理完过期元素和队尾较小元素后，把当前下标 i 入队。等 i >= k-1 时，说明第一个完整窗口已经形成，此时队首就是当前窗口最大值，把 nums[queue[0]] 加入答案即可。每个下标最多入队一次、出队一次，所以总时间复杂度是 O(n)，空间复杂度是 O(k)。

知识边界#

• 单调队列维护的是“候选最大值”的下标，队列中的值从队首到队尾保持递减，队首永远是当前窗口最大值。
• 队列里必须存下标，因为窗口会移动，需要用 queue[0] <= i-k 判断元素是否已经过期。
• 队尾弹出条件使用 <=，表示遇到相同值时保留更新的下标；这样旧的相同值更早过期，留着也没有额外价值。
• 虽然代码里有内层 for，但每个元素只会被加入和弹出有限次，因此整体不是 O(nk)，而是 O(n)。
• 这份实现默认输入满足原题约束：1 <= k <= len(nums)。

代码#

好啦，思路说清楚了，代码就按“先清过期、再维护单调、最后收答案”的顺序写下来：

func maxSlidingWindow(nums []int, k int) []int {
	queue := make([]int, 0)
	ans := make([]int, 0)
	for i, n := range nums {
		// 1. 删除窗口左边界之外的下标
		if len(queue) > 0 && queue[0] <= i-k {
			queue = queue[1:]
		}

		// 2. 维护单调递减队列
		// 如果队尾元素 <= 当前元素，它以后不可能成为最大值
		for len(queue) > 0 && nums[queue[len(queue)-1]] <= n {
			queue = queue[:len(queue)-1]
		}

		// 3. 当前下标入队
		queue = append(queue, i)

		// 4. 从第 k 个元素开始记录答案
		if i >= k-1 {
			ans = append(ans, nums[queue[0]])
		}
	}
	return ans
}

这题的重点不是“窗口”两个字，而是怎么只留下未来还有用的元素。等队列排好队，最大值就一直站在最前面啦。