滑動視窗演算法基本資訊
滑動視窗演算法用於對給定大緩衝區或陣列的特定視窗大小執行所需操作。視窗從第一個元素開始，並一直向右移動一個元素。目標是找到每個視窗中存在的最小 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)