滑动窗口算法基本信息

滑动窗口算法用于对给定大缓冲区或阵列的特定窗口大小执行所需操作。窗口从第一个元素开始，并一直向右移动一个元素。目标是找到每个窗口中存在的最小 k 数。这通常称为滑动窗口问题或算法。

例如，为了从给定数组中的每个 n 元素中找到最大或最小元素，使用滑动窗口算法。

例：

输入数组： [1 3 -1 -3 5 3 6 7]

窗口大小： 3

**** 输入数组的每 3 个元素的最大元素：

+---------------------------------+---------+
|      Windows Position           |   Max   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |    3    |
+------------+----+---+---+---+---+---------+
| `1` |[3   -1   -3]| 5 | 3 | 6 | 7 |    3    |
+---+-------------+---+---+---+---+---------+
| `1` | 3 |[-1   -3   5]| 3 | 6 | 7 |    5    |
+---+---+-------------+---+---+---+---------+
| `1` | 3 | -1 |[-3   5   3]| 6 | 7 |    5    |
+---+---+----+------------+---+---+---------+
| `1` | 3 | -1 | -3 |[5   3   6]| 7 |    6    |
+---+---+----+----+-----------+---+---------+
| `1` | 3 | -1 | -3 | 5 |[3   6   7]|    7    |
+---+---+----+----+---+-----------+---------+

**** 输入数组的每 3 个元素的最小元素：

+---------------------------------+---------+
|      Windows Position           |   Min   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |   -1    |
+------------+----+---+---+---+---+---------+
| `1` |[3   -1   -3]| 5 | 3 | 6 | 7 |   -3    |
+---+-------------+---+---+---+---+---------+
| `1` | 3 |[-1   -3   5]| 3 | 6 | 7 |   -3    |
+---+---+-------------+---+---+---+---------+
| `1` | 3 | -1 |[-3   5   3]| 6 | 7 |   -3    |
+---+---+----+------------+---+---+---------+
| `1` | 3 | -1 | -3 |[5   3   6]| 7 |    3    |
+---+---+----+----+-----------+---+---------+
| `1` | 3 | -1 | -3 | 5 |[3   6   7]|    3    |
+---+---+----+----+---+-----------+---------+

找到 3 元素之和的方法：

方法 1：

第一种方法是使用快速排序，当枢轴位于第 K 位置时，右侧的所有元素都大于枢轴，因此，左侧的所有元素自动变为给定数组的 K 个最小元素。

方法 2：

保留一个 K 元素数组，用给定输入数组的前 K 个元素填充它。现在从 K + 1 元素，检查当前元素是否小于辅助数组中的最大元素，如果是，则将此元素添加到数组中。上述解决方案的唯一问题是我们需要跟踪最大元素。仍然可行。我们如何跟踪整数集中的最大元素？想堆。想想最大堆。

方法 3：

大！ 在 O(1) 中，我们将获得已经选择为最小 K 元素的 K 个元素中的 max 元素。如果当前集合中的 max 大于新考虑的元素，我们需要删除 max 并在 K 最小元素集合中引入新元素。再次 Heapify 以维护堆属性。现在我们可以轻松地在 N 的数组中获得 K 个最小元素。

太空辅助： O(n)

时间复杂性： O(n)