什么是滑动窗口？

什么是滑动窗口？

假设有一个数组 [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)。