『剣指offer』ブラシノート(スタックとキュー):スライドウィンドウの最大値

『剣指offer』ブラシノート(スタックとキュー):スライドウィンドウの最大値

転載作者と出典を明記してください:http://blog.csdn.net/u011475210

コードアドレス:https://github.com/WordZzzz/Note/tree/master/AtOffer

ブラシ問題プラットフォーム:https://www.nowcoder.com/

題

編  者:WordZzzz

剣指offerブラシノートスタックとキュースライドウィンドウの最大値

タイトル説明

解題構想

C版コード実装

タイトルの説明
配列とスライドウィンドウのサイズを指定し、すべてのスライドウィンドウの数値の最大値を見つけます.例えば、配列{2,3,4,2,6,2,5,1}およびスライドウィンドウのサイズ3を入力すると、合計6つのスライドウィンドウが存在し、それらの最大値はそれぞれ{4,4,6,6,6,6,5}である.配列{2,3,4,2,6,2,5,1}に対するスライド窓は,{[2,3,4],2,6,2,5,1},{3,4,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],{2,3,4,2,6,[2,5],{2,5,1},{2,3,4,2,5,{2,5,1}}の6つである
問題を解く構想.
実際には、スライドウィンドウはキューと見なすことができます.ウィンドウがスライドすると、ウィンドウの最初の数値が削除され、ウィンドウの最後に新しい数値が追加されます.これは、キューの先進的な先発機能に合致します.残りのタスクは、キューから最大値を見つける方法です.
以前はO(1)時間で最小値を得るスタックと,2つのスタックでキューを実現する問題があり,結合すればコードを書きやすくなる.全時間複雑度はO(n)であった.
しかし、ここでは、2つの問題を書くコードに相当するため、上記の方法を使用するつもりはありません.大きさよりも一歩をスタックに入れる前に置くと、状況がよくなるのではないかと考えてみましょう.
STLにおけるdequeを用いて実現することができ,次に配列{2,3,4,2,6,2,5,1}を例に全体的な考え方を詳しく述べる.
配列の最初の数字は2で、キューに格納されます.2番目の数字は3で、2より大きいので、2がスライドウィンドウの最大値になるはずがないので、2をキューから削除し、3をキューに格納します.3番目の数字は4で、3より大きく、同じ削除3は4を保存します.スライドウィンドウにはすでに3つの数字があり、その最大値4はキューのヘッダにあります.
4番目の数字は2対4で小さいが、4が滑り出した後も最大値になる可能性があるので、2をキューの末尾に格納します.次の数字は6で、4と2より大きくて、4と2を削除して、6を保存します.このように順次行われ、最大値は常にキューのヘッダに位置します.
しかし、スライドウィンドウに数字が含まれているかどうかをどのように判断しますか?数値ではなく、列に数字の下付き文字を格納する必要があります.1つの数字の下付き文字と現在処理されている数字の下付き文字の差がスライドウィンドウの大きさ以上である場合、この数字はウィンドウからスライドされ、キューから削除できます.

次のコードでは、indexはスライド窓の最大値である可能性のある数字の下付き文字を保存するための両端開口のキューです.1つの数字の下付き文字を格納する前に、まずキューに格納される数字が格納される数字より小さいかどうかを判断します.既存の数字が格納される数字より小さい場合、これらの数字はスライドウィンドウの最大値ではありません.これにより、キューの末尾から順に削除されます(pop_backが呼び出されます).また、キューの先頭の数字がウィンドウから滑り出した場合、滑り出した数字もキューの先頭から削除される必要があります(pop_frontが呼び出されます).キューの先頭と末尾ともに数字が削除される可能性があるため、2つの開口部が必要なキューの原因にもなります.
C++版コード実装

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> maxInWindows;
        if(num.size() >= size && size >= 1){
            deque<int> index;
            for(unsigned int i = 0; i < size; ++i){
                while(!index.empty() && num[i] >= num[index.back()])
                    index.pop_back();
                index.push_back(i);
            }
            for(unsigned int i = size; i < num.size(); ++i){
                maxInWindows.push_back(num[index.front()]);
                while(!index.empty() && num[i] >= num[index.back()])
                    index.pop_back();
                if(!index.empty() && index.front() <= (int)(i-size))
                    index.pop_front();
                index.push_back(i);
            }
            maxInWindows.push_back(num[index.front()]);
        }
        return maxInWindows;
    }
};

シリーズチュートリアル継続リリース中、購読、注目、コレクション、コメント、いいね～(￣▽￣)～
完の汪(′▽`▽`)｡｡｡zz