什么是滑动窗口?
作者:野牛程序员:2024-10-21 16:37:10数据结构阅读 2283
什么是滑动窗口?
什么是滑动窗口?
假设有一个数组 [10, 3, 5, 8, 7, 6, 4, 2, 9, 1]
,给定一个窗口大小 k = 3
,滑动窗口就是一个在数组上连续滑动的子数组,每次只向右移动一个位置,窗口内的元素总是连续的。
例如,数组的前几个滑动窗口可以这样理解:
第1个窗口是数组的前3个元素
[10, 3, 5]
,其中最小值是3
。第2个窗口是
[3, 5, 8]
,最小值是3
。第3个窗口是
[5, 8, 7]
,最小值是5
。以此类推,直到窗口滑动到数组的末尾。
举例说明滑动窗口最小值:
假设数组是 [10, 3, 5, 8, 7, 6, 4, 2, 9, 1]
,窗口大小 k = 3
。
滑动窗口的每个位置和对应的最小值如下:
第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
。
因此,最终的输出应该是每个窗口的最小值列表:[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
- 上一篇:arduino声控灯
- 下一篇:c++递归实现二分查找