Go语言滑动窗口最大值的实现示例

目录

• 一、问题描述与示例
• 示例
• 二、常见解法分析
• 1. 暴力解法（Brute Force）
• 2. 优化解法：单调队列（Monotonic Queue）
• 核心思想
• 三、Go语言代码实现（单调队列法）
• 四、关键步骤详解
• 五、复杂度分析
• 六、工程应用场景
• 七、常见变种
• 八、测试与验证
• 九、总结

在高性能计算、数据分析、监控系统等应用中，实时处理数据流是一项基础能力。其中一个典型的需求是：在一个不断移动的区间（窗口）内，快速求出当前区间的最大值。这就是我们今天要实现的算法——滑动窗口最大值（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

最直观的方式是：每次滑动窗口后，遍历窗口中所有元素，找最大值。

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 时，暴力解法会非常慢。

为了提升效率，我们可以使用双端队列（Deque）实现一个单调递减队列。

• 队列存下标，而非值；
• 队列内下标对应的值保持从队头到队尾递减，这样队首元素就是当前窗口最大值；
• 每次新元素加入时：
  • 移除队尾小于当前值的下标；
  • 将当前下标加入队尾；
• 检查队首是否超出窗口范围（deque[0] <= i - k），如果是则弹出。

这种方式保证了每个元素最多进出队列一次，整体时间复杂度为 O(n)。

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]
}

• 队列存下标而非值
  • 方便判断是否超出窗口范围；
  • 通过 nums[deque[0]] 获取最大值。
• 保持递减顺序
  • 只有比当前值大的元素才可能在未来成为最大值；
  • 小于当前值的元素直接被淘汰。
• 滑动与淘汰
  • 每次滑动都要检查队首是否还在窗口内；
  • 淘汰不在窗口范围的下标。

• 时间复杂度：O(n)
  每个元素最多被加入和移出队列一次。
• 空间复杂度：O(k)
  队列最多存储 k 个下标。

• 系统性能监控
  • 在固定时间窗口内找CPU利用率的峰值。
• 金融数据分析
  • 计算股票价格的滑动最大值，用于趋势判断。
• 信号处理
  • 检测信号峰值，常用于音频分析、网络流量监控。

• 滑动窗口最小值：只需将单调递减队列改为递增队列。
• 滑动窗口平均值/中位数：需要更复杂的数据结构（如堆、平衡树）。
• 二维滑动窗口最大值：可扩展至图像处理，如卷积操作。

我们可以编写单元测试：

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) 时间内解决问题，适合大数据场景；
• 掌握该技巧有助于解决其他类似的区间统计问题。

 到此这篇关于Go语言滑动窗口最大值的实现示例的文章就介绍到这了,更多相关Go语言滑动窗口最大值内容请搜索风君子博客以前的文章或继续浏览下面的相关文章希望大家以后多多支持风君子博客！

您可能感兴趣的文章:

• JavaScript日拱算法题解滑动窗口的最大值示例
• Java C++分别实现滑动窗口的最大值
• Java 滑动窗口最大值的实现