滑动窗口最大值

怎样从“窗口 k=3,每个窗口最大值。”推导出 单调队列 · 滑窗最大，并证明每次状态变化都不会漏掉答案？

中心结论：双端队列存下标,保持递减;队头即窗口 max。

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

在本站主例中，窗口 k=3,每个窗口最大值。

算法最终需要得到或观察：各窗口 max 序列。

为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
2. 2状态只维护 deque 下标、L/R 窗口。
3. 3转移每一步按照 双端队列存下标,保持递减;队头即窗口 max。
4. 4收尾读取 各窗口 max 序列。，并复核边界与复杂度。

栈或队列中保存的是仍未找到结论、且保持单调关系的下标。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：deque 下标、L/R 窗口。

给定一个数组和一个窗口为 K 的窗口，当窗口从数组的左边滑动到数组右边的时候，输出每次移动窗口以后，在窗口内的最大值。 这道题最暴力的方法就是 2 层循环，时间复杂度 O(n K)。 另一种思路是用优先队列，每次窗口以后的时候都向优先队列里面新增一个节点，并删除一个节点。时间复杂度是 O(n log n) 最优的解法是用双端队列，队列的一边永远都存的是窗口的最大值，队列的另外一个边存的是比最大值小的值。队列中最大值左边的所有值都出队。在保证了双端队列的一边即是最大值以后，时间复杂度是 O(n)，空间复杂度是 O(K)

双端队列存下标,保持递减;队头即窗口 max。

执行过程中持续维护：deque 下标、L/R 窗口。

正确性依赖以下不变量：队列存潜在 max,过期下标弹左。

面试时可以压缩为：单调队列 O(n)。

落到当前题，执行机制可以压缩为：双端队列存下标,保持递减;队头即窗口 max。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入窗口 k=3,每个窗口最大值。 因为：双端队列存下标,保持递减;队头即窗口 max。
2. 2窗口 [0,2] 最大值 3窗口形成,记录最大值。 因为：deque 维护候选最大值。
3. 3窗口 [1,3] 最大值 3窗口形成,记录最大值。 因为：deque 维护候选最大值。
4. 4窗口 [2,4] 最大值 5窗口形成,记录最大值。 因为：deque 维护候选最大值。
5. 5窗口 [3,5] 最大值 5窗口形成,记录最大值。 因为：deque 维护候选最大值。
6. 6窗口 [5,7] 最大值 7窗口形成,记录最大值。 因为：deque 维护候选最大值。
7. 7结果 3,3,5,5,6,7扫描结束。 因为：O(n) 每个下标进出 deque 一次。
8. 8收尾与复杂度各窗口 max 序列。 因为：时间 O(n) · 空间 O(k) 辅助；含输出 O(n-k+1)。双端队列存下标,保持递减;队头即窗口 max。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 暴力解法 O(nk)
func maxSlidingWindow1(a []int, k int) []int {
	res := make([]int, 0, k)
	n := len(a)
	if n == 0 {
		return []int{}
	}
	for i := 0; i <= n-k; i++ {
		max := a[i]
		for j := 1; j < k; j++ {
			if max < a[i+j] {
				max = a[i+j]
			}
		}
		res = append(res, max)
	}

	return res
}

// 解法二 双端队列 Deque
func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 || len(nums) < k {
		return make([]int, 0)
	}
	window := make([]int, 0, k) // store the index of nums
	result := make([]int, 0, len(nums)-k+1)
	for i, v := range nums { // if the left-most index is out of window, remove it
		if i >= k && window[0] <= i-k {
			window = window[1:]
		}
		for len(window) > 0 && nums[window[len(window)-1]] < v { // maintain window
			window = window[0 : len(window)-1]
		}
		window = append(window, i) // store the index of nums
		if i >= k-1 {
			result = append(result, nums[window[0]]) // the left-most is the index of max value in nums
		}
	}
	return result
}

func main() {
    // 1. 主例
    //    输入：mode="sliding-window-max", nums=[1,3,-1,-3,5,3,6,7], k=3
    //    期望：各窗口 max 序列。
    //
    // 2. 失败 / 未命中
    //    检查：存值不存下标无法判过期。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC3 滑窗；LC1438 绝对差
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意窗口 k=3,每个窗口最大值。
2. 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
3. 3优化双端队列存下标,保持递减;队头即窗口 max。
4. 4证明队列存潜在 max,过期下标弹左。
5. 5复杂度时间 O(n)，空间 O(k) 辅助；含输出 O(n-k+1)