在高性能计算、数据分析、监控系统等应用中，实时处理数据流是一项基础能力。其中一个典型的需求是：在一个不断移动的区间（窗口）内，快速求出当前区间的最大值。这就是我们今天要实现的算法——滑动窗口最大值（Sliding Window Maximum）。
一、问题描述与示例
给定一个整数数组 nums 和一个整数 k（窗口大小），我们需要输出一个数组，表示从左到右依次滑动窗口后，每个窗口中的最大值。
示例
输入： nums = [1,3,-1,-3,5,3,6,7], k = 3 输出： [3,3,5,5,6,7]
解释：
- • 窗口
[1,3,-1]→ 最大值 3 - • 窗口
[3,-1,-3]→ 最大值 3 - • 窗口
[-1,-3,5]→ 最大值 5 - • 窗口
[-3,5,3]→ 最大值 5 - • 窗口
[5,3,6]→ 最大值 6 - • 窗口
[3,6,7]→ 最大值 7
二、常见解法分析
1. 暴力解法（Brute Force）
最直观的方式是：每次滑动窗口后，遍历窗口中所有元素，找最大值。
func MaxSlidingWindowBrute(nums []int, k int) []int { var result []int for i := 0; i <= len(nums)-k; i++ { maxVal := nums[i] for j := i; j < i+k; j++ { if nums[j] > maxVal { maxVal = nums[j] } } result = append(result, maxVal) } return result }
复杂度分析：
- • 时间复杂度：O(n*k)
- • 空间复杂度：O(1)
当 n 较大、k 较大时，这种方法性能较差。例如 n=10^5, k=500 时，暴力解法会非常慢。
2. 优化解法：单调队列（Monotonic Queue）
为了提升效率，我们可以使用双端队列（Deque）实现一个单调递减队列。
核心思想
- 1. 队列存下标，而非值；
- 2. 队列内下标对应的值保持从队头到队尾递减，这样队首元素就是当前窗口最大值；
- 3. 每次新元素加入时：
- • 移除队尾小于当前值的下标；
- • 将当前下标加入队尾；
- 4. 检查队首是否超出窗口范围（
deque[0] <= i - k），如果是则弹出。
这种方式保证了每个元素最多进出队列一次，整体时间复杂度为 O(n)。
三、Go语言代码实现（单调队列法）
package main import ( "fmt" ) // MaxSlidingWindow 求解滑动窗口最大值 func MaxSlidingWindow(nums []int, k int) []int { if len(nums) == 0 || k == 0 { return []int{} } var result []int deque := []int{} // 存储下标 for i, v := range nums { // 1. 移除队尾比当前元素小的下标 for len(deque) > 0 && nums[deque[len(deque)-1]] < v { deque = deque[:len(deque)-1] } // 2. 添加当前元素下标 deque = append(deque, i) // 3. 移除超出窗口范围的队首下标 if deque[0] <= i-k { deque = deque[1:] } // 4. 当窗口形成后，将队首对应的值加入结果 if i >= k-1 { result = append(result, nums[deque[0]]) } } return result } func main() { nums := []int{1, 3, -1, -3, 5, 3, 6, 7} k := 3 fmt.Println(MaxSlidingWindow(nums, k)) // [3 3 5 5 6 7] }
四、关键步骤详解
- 1. 队列存下标而非值
- • 方便判断是否超出窗口范围；
- • 通过
nums[deque[0]]获取最大值。
- 2. 保持递减顺序
- • 只有比当前值大的元素才可能在未来成为最大值；
- • 小于当前值的元素直接被淘汰。
- 3. 滑动与淘汰
- • 每次滑动都要检查队首是否还在窗口内；
- • 淘汰不在窗口范围的下标。
五、复杂度分析
- • 时间复杂度：O(n)
每个元素最多被加入和移出队列一次。 - • 空间复杂度：O(k)
队列最多存储k个下标。
六、工程应用场景
- 1. 系统性能监控
- • 在固定时间窗口内找CPU利用率的峰值。
- 2. 金融数据分析
- • 计算股票价格的滑动最大值，用于趋势判断。
- 3. 信号处理
- • 检测信号峰值，常用于音频分析、网络流量监控。
七、常见变种
- 1. 滑动窗口最小值：只需将单调递减队列改为递增队列。
- 2. 滑动窗口平均值/中位数：需要更复杂的数据结构（如堆、平衡树）。
- 3. 二维滑动窗口最大值：可扩展至图像处理，如卷积操作。
八、测试与验证
我们可以编写单元测试：
func TestMaxSlidingWindow(t *testing.T) { tests := []struct { nums []int k int want []int }{ {[]int{1,3,-1,-3,5,3,6,7}, 3, []int{3,3,5,5,6,7}}, {[]int{9,10,9,-7,-4,-8,2,-6}, 5, []int{10,10,9,2}}, } for _, tt := range tests { got := MaxSlidingWindow(tt.nums, tt.k) if !reflect.DeepEqual(got, tt.want) { t.Errorf("nums=%v k=%d got=%v want=%v", tt.nums, tt.k, got, tt.want) } } }
九、总结
- • 滑动窗口最大值问题是经典的单调队列应用；
- • 暴力解法易实现但性能低；
- • 单调队列解法能在 O(n) 时间内解决问题，适合大数据场景；
- • 掌握该技巧有助于解决其他类似的区间统计问题。
