当前位置:首页数据结构 > 正文

什么是滑动窗口?

作者:野牛程序员:2024-10-21 16:37:10数据结构阅读 2283
什么是滑动窗口?

什么是滑动窗口?

假设有一个数组 [10, 3, 5, 8, 7, 6, 4, 2, 9, 1],给定一个窗口大小 k = 3,滑动窗口就是一个在数组上连续滑动的子数组,每次只向右移动一个位置,窗口内的元素总是连续的。

例如,数组的前几个滑动窗口可以这样理解:

  1. 第1个窗口是数组的前3个元素 [10, 3, 5],其中最小值是 3

  2. 第2个窗口是 [3, 5, 8],最小值是 3

  3. 第3个窗口是 [5, 8, 7],最小值是 5

  4. 以此类推,直到窗口滑动到数组的末尾。

举例说明滑动窗口最小值:

假设数组是 [10, 3, 5, 8, 7, 6, 4, 2, 9, 1],窗口大小 k = 3

滑动窗口的每个位置和对应的最小值如下:

  1. 第1个窗口是 [10, 3, 5],最小值为 3

  2. 第2个窗口是 [3, 5, 8],最小值为 3

  3. 第3个窗口是 [5, 8, 7],最小值为 5

  4. 第4个窗口是 [8, 7, 6],最小值为 6

  5. 第5个窗口是 [7, 6, 4],最小值为 4

  6. 第6个窗口是 [6, 4, 2],最小值为 2

  7. 第7个窗口是 [4, 2, 9],最小值为 2

  8. 第8个窗口是 [2, 9, 1],最小值为 1

因此,最终的输出应该是每个窗口的最小值列表:[3, 3, 5, 6, 4, 2, 2, 1]

形象比喻:

假设有一个窗口正在从左向右滑动,通过每次移动,窗口内的元素逐渐变化。目标是记录每个窗口内的最小值。

窗口示例图:

初始数组:       [10, 3, 5, 8, 7, 6, 4, 2, 9, 1]
第1个窗口 ->   [10, 3, 5]  -> 最小值 3
第2个窗口 ->      [3, 5, 8]  -> 最小值 3
第3个窗口 ->         [5, 8, 7]  -> 最小值 5
第4个窗口 ->            [8, 7, 6]  -> 最小值 6
第5个窗口 ->               [7, 6, 4]  -> 最小值 4
第6个窗口 ->                  [6, 4, 2]  -> 最小值 2
第7个窗口 ->                     [4, 2, 9]  -> 最小值 2
第8个窗口 ->                        [2, 9, 1]  -> 最小值 1

实际应用场景:

滑动窗口最小值的计算在许多实际场景中非常有用,比如:

  • 图像处理中的滤波器计算(窗口滤波)。

  • 实时数据的最优选择。

  • 股票市场的滚动时间段中的最小值计算等。

通过单调队列,可以高效地解决这一问题,确保时间复杂度为 O(n)。


野牛程序员教少儿编程与信息学奥赛-微信|电话:15892516892
野牛程序员教少儿编程与信息学竞赛-微信|电话:15892516892
  • 滑动窗口
  • 相关推荐

    最新推荐

    热门点击