スライディングウィンドウの最大値をjsで実現するアルゴリズム

この記事では、js でスラ​​イディング ウィンドウの最大値を実現するためのアルゴリズムを紹介します。困っている人はぜひ参考にしてください。

問題の説明

配列とスライディング ウィンドウのサイズが与えられた場合、スライディング ウィンドウ内のすべての値の最大値を見つけます。たとえば、入力配列が {2,3,4,2,6,2,5,1} で、スライディング ウィンドウのサイズが 3 の場合、合計 6 つのスライディング ウィンドウとその最大値が存在します。は {4,4,6, 6,6,5}; 配列 {2,3,4,2,6,2,5,1} には次の 6 つのスライディング ウィンドウがあります: {[2,3, 4],2,6,2,5 ,1}、{2,[3,4,2],6,2,5,1}、{2,3,[4,2,6],2,5 ,1}、{2,3,4 ,[2,6,2],5,1}、{2,3,4,2,[6,2,5],1}、{2,3,4 ,2,6,[2,5,1]}。

分析

よく考えてください。配列 {2,3,4,2,6,2,5,1} の場合、ウィンドウ サイズが 3 の場合、プロセス全体は次のようになります:

1. {[2,3,4],2,6,2,5,1}、この時の最大値は4

2. {2,[3,4,2],6,2,5 ,1}、この最大値は 4

3. {2,3,[4,2,6],2,5,1} です。新しいエントリ ウィンドウが 6 であるため、この時点の最大値は 6 です。 4

4. {2,3,4,[2,6,2],5,1}より大きい場合、このときの最大値は6

5. {2,3,4,2,[6 ,2,5],1}、この時の最大値は6

6. {2,3,4,2,6,[2,5,1]}、この時の最大値は5

アイデアは次のとおりです:

現在のウィンドウの最大値の配列添字を maxIndex として保存します。 maxIndex がまだウィンドウ内にある場合は、maxIndex の値と最新の値を比較するだけで済みます。新しく入力された値が大きい場合は、maxIndex を更新します。それ以外の場合、maxIndex がウィンドウ内にない場合は、すべての値を調べる必要があります。現在のウィンドウで新しい maxIndex を見つけます

コードの実装

function maxInWindows(arr, size)
{
    if(size > arr.length || size === 0)
        return [];
    var res = [], maxIndex = -1;
    for(var l = 0, r = size-1;r < arr.length;l++, r++){
        if(maxIndex < l){
            maxIndex = getMaxIndex(arr, l, r);
        }
        if(arr[r] > arr[maxIndex]){
            maxIndex = r;
        }
        res.push(arr[maxIndex]);
    }

    return res;
}
function getMaxIndex(arr, l, r){
    var index = l;
    for(var i = l;i <= r;i++) {
        if(arr[i] > arr[index])
            index = i;
    }
    return index;
}

関連する推奨事項:

js で 2 つのスタックを使用してキューを実装するアルゴリズム

jquery で $() 関数を使用する方法

以上がスライディングウィンドウの最大値をjsで実現するアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。