各アルゴリズム問題のスライドウィンドウの最大値を真剣に扱う

スライドウィンドウと配列をあげます.スライドウィンドウは配列の最初の要素から後ろにスライドし、スライドするたびに現在のウィンドウの対応する配列要素の最大値を計算します.
ウィンドウ長をm、配列長をnに設定し、O(n*m)アルゴリズムがあり、最も大きなO(n*lgm)で計算し、比較した要素間の関係を利用したO(n)アルゴリズムである.
 
ブログから http://blog.csdn.net/sgbfblog/article/details/7967489
 
タイトルの説明
配列A[]が与えられ、一番左から最後のエッジまでスライドするwサイズのスライドウィンドウがある.このウィンドウにはw個の数字しか見えず、毎回1つの位置しか移動できません.我々の目的は,各ウィンドウw個の数字の最大値を見つけ,これらの最大値を配列Bに格納することである.
例えば配列A=[13−1−35 3 6 7]であり、ウィンドウサイズwは3である.ウィンドウのスライド処理は次のようになります.
 

Window 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



       A w  

     B，  B[i]   A[i] A[i+w-1] w       。

 
一、簡単な解法
最も簡単な考え方は,移動するたびにw個の数字の最大値を計算して保存し,w個の数字の最大値を計算するたびにO(w)の時間を必要とし,スライド過程ではn−w+1回スライドし,nは配列サイズであるため,合計時間はO(nw)である.コードは次のとおりです.
 
[cpp] 
view plain
copy
 
/*最大スライドウィンドウメイン関数*/  

void maxSlidingWindow(int A[], int n, int w, int B[])   

{  

    for (int i=0; i<=n-w; i++)   

        B[i] = max(A+i, w);  

}  

  

/*配列の最大値を求めます*/  

int max(int A[], int n)  

{  

    int max = A[0];  

    for (int i=1; i
        if (A[i] > max) {  

            max = A[i];  

        }  

    }  

    return max;  

}  

 
二、最大炉解法
第1の方法は考え方が簡単であるが、時間の複雑さが高すぎるため、改善が必要である.最大スタックを使用してw個の数字を保存することができ、数字を挿入するたびにO(lgw)の時間しか必要とせず、スタックから最大値を取るにはO(1)の時間しか必要としない.ウィンドウが左から右にスライドするにつれて、スタックの中のいくつかの数字は失効する(ウィンドウに含まれないため).
 
[cpp] 
view plain
copy
 
typedef pair Pair;  

void maxSlidingWindow(int A[], int n, int w, int B[])  

{  

    priority_queue Q; //優先キューウィンドウの値を保存  

    for (int i = 0; i < w; i++)  

        Q.push(Pair(A[i], i));  //w個の要素の最大スタックを構築する  

    for (int i = w; i < n; i++) {  

        Pair p = Q.top();  

        B[i-w] = p.first;  

        while (p.second <= i-w) {  

            Q.pop();  

            p = Q.top();  

        }  

        Q.push(Pair(A[i], i));  

    }  

    B[n-w] = Q.top().first;  

}  
配列自体が秩序化されている場合、中のwhileサイクルは実行されず、スタックサイズはnに増大する.スタックサイズはwに一定に保たれないため、このアルゴリズムの時間複雑度はO(nlgn)である.
 
 
三、双方向キューO(N)解法
最大ヒープ解法は、元のヒープの要素が[105 3]、新しい要素が11のような冗長な要素をヒープに保存します.このとき、ヒープには[11 5 3]が保存されます.実際には、キュー全体を空にしてから、11をキューに追加することができます.つまり、キューにのみ[11]を保持します.を使用します.双方向キューを使用すると、スライドウィンドウの最大値は常にキューの先頭に保存され、キュー内のデータは常に大から小に並べられます.現在のスライドウィンドウの最大値よりも大きい値に遭遇した場合、キューは空になり、新しい最大値がキューに挿入されます.現在の最大値より小さい値に遭遇した場合は、キューの末尾に直接挿入されます.移動するたびに動くときは現在の最大値が有効範囲にあるかどうかを判断し、いない場合はキューから削除する必要があります.このアルゴリズムの時間複雑度は、要素ごとに最大エンキューとエンキューが1回ずつあるため、O(N)です.
 
[cpp] 
view plain
copy
 
void maxSlidingWindow(int A[], int n, int w, int B[])   

{  

  deque Q;  

  for (int i = 0; i < w; i++) {  

    while (!Q.empty() && A[i] >= A[Q.back()])  

      Q.pop_back();  

    Q.push_back(i);  

  }  

  for (int i = w; i < n; i++) {  

    B[i-w] = A[Q.front()];  

    while (!Q.empty() && A[i] >= A[Q.back()])  

      Q.pop_back();  

    while (!Q.empty() && Q.front() <= i-w)  

      Q.pop_front();  

    Q.push_back(i);  

  }  

  B[n-w] = A[Q.front()];  

}