(C++)剣指offer-64:スライドウィンドウが最大値(キュー)

(C++)剣指offer-64:スライドウィンドウが最大値
双方向単調キューで実現することで、ウィンドウを右にスライドさせるプロセスは、ウィンドウの最初の数字を削除することに相当し、ウィンドウの最後に新しい数字を追加することで、双方向キューdequeを実現することができ、キューにはウィンドウの最大要素になる可能性のある数字しか残っていないため、キューには大きな数字が入ります.このキューの中でこれより小さい数字のすべてをポップアップし、双方向単調キューを通じて要素の下付き文字を記憶し、双方向キューのキューヘッダがキュー全体の最大要素の下付き文字であると仮定し、キューの最後の下付き文字が表す要素の数値が順次減少するため、配列全体を巡る際にキューに残るかどうかを判断し、キューヘッダの下付きスケール距離iがkを超える場合は、キューを出なければならない.num[i]を介して、それより小さいキュー要素の下付きスケールをすべてポップアップし、キューの単調性を保証する.これにより、ループが完了すると、各キューヘッダはスライドウィンドウの最大値の下付きスケールであり、時間複雑度はO(n)であり、具体的なコードは以下の通りである.

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