什么是滑动窗口？

什么是滑动窗口？

假设有一个数组 ，给定一个窗口大小 ，滑动窗口就是一个在数组上连续滑动的子数组，每次只向右移动一个位置，窗口内的元素总是连续的。

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

1. 第1个窗口是数组的前3个元素 ，其中最小值是 。

2. 第2个窗口是 ，最小值是 。

3. 第3个窗口是 ，最小值是 。

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

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

假设数组是 ，窗口大小 。

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

1. 第1个窗口是 ，最小值为 。

2. 第2个窗口是 ，最小值为 。

3. 第3个窗口是 ，最小值为 。

4. 第4个窗口是 ，最小值为 。

5. 第5个窗口是 ，最小值为 。

6. 第6个窗口是 ，最小值为 。

7. 第7个窗口是 ，最小值为 。

8. 第8个窗口是 ，最小值为 。

因此，最终的输出应该是每个窗口的最小值列表：。

形象比喻：

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

窗口示例图：

初始数组:       [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)。