algorithm
スライディングウィンドウアルゴリズム

スライディングウィンドウアルゴリズム基本情報

スライディングウィンドウアルゴリズムは、所与の大きなバッファまたはアレイの特定のウィンドウサイズに対して必要な操作を実行するために使用される。ウィンドウは最初の要素から始まり、1つの要素だけ右にシフトし続けます。目的は、各ウィンドウに存在する最小の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：

第1の方法は、ピボットがK番目の位置にあるとき、右辺のすべての要素がピボットよりも大きいので、左辺のすべての要素が自動的に与えられた配列のK個の最小要素になるクイックソートを使用することです。

方法2：

K要素の配列を保持し、与えられた入力配列の最初のK要素で満たします。今度はK + 1要素から、現在の要素が補助配列の最大要素よりも小さいかどうかをチェックし、そうであればこの要素を配列に追加します。上記の解決策で問題になるのは、最大要素を追跡する必要があることだけです。まだ実行可能です。どのようにして整数の集合の最大要素を追跡することができますか？ヒープを考えよう。最大ヒープを考えてください。

方法3：

すばらしいです！ O（1）では、既に最小のK個の要素として選択されたK個の要素の中からmax要素を得る。現在の集合の中の最大値が新たに考慮された要素よりも大きい場合、maxを除去し、K最小の要素の集合における新しい要素を導入する必要がある。ヒーププロパティを維持するために再びヒープ化します。今度は、Kの最小要素をNの配列で簡単に得ることができます。

スペース補助： O(n)

時間の複雑さ： O(n)

C＃におけるスライディングウィンドウアルゴリズムの実装

public class SlidingWindow
{
    public static int[] MaxSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var max = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] > max) max = input[i + j];
            }
            result[i] = max;
        }
        return result;
    }

    public static int[] MinSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var min = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] < min) min = input[i + j];
            }
            result[i] = min;
        }
        return result;
    }

    public static int[] MainMax(int[] input, int n)
    {
        return MaxSlidingWindow(input, n);
    }

    public static int[] MainMin(int[] input, int n)
    {
        return MinSlidingWindow(input, n);
    }
}