Leetcode:239. Sliding Window Maximum (c++)

Problem:
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,Given nums =  [1,3,-1,-3,5,3,6,7] , and k = 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

Therefore, return the max sliding window as  [3,3,5,5,6,7] .
Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
タイトル:
配列numsが与えられ、kサイズのスライドウィンドウが配列の一番左側から配列の一番右側に移動する.スライドウィンドウk内の数字しか見えません.スライドウィンドウは毎回1つだけ右に移動します.
たとえば、
nums＝[1,3,-1,-3,5,3,6,7]とk＝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       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,3,5,5,6,7]であることがわかる.
注意:
kは常に有効であると仮定することができます.例えば、1≦k≦入力配列の大きさであり、入力配列は空ではありません.
ステップ:
線形時間の複雑さでこの問題を解決できますか?
分析:
numsの長さnを仮定すると,通常の思考はウィンドウ内の最大値を判断するたびに(n−k)回,各ウィンドウ内にk個の要素があるため複雑度は
(n - k) * k ; このように線形時間の複雑さを満たさないで、私たちは正常な思考の解法が繰り返し操作があるかどうかを見てみましょう.例えば、最初のウィンドウの最大値を判断した後、2番目のウィンドウの時、最初のウィンドウと2番目のウィンドウが交差する座標が繰り返し判断したことを発見しました.チェーンテーブルの最初の要素は前回のウィンドウで判断した最大値で、最後の最初の要素は最小値で、numsの新しい要素が来たら、私たちは4つの操作があります:(チェーンテーブルはnumsのindex、つまり1,2,3,4....)
(1)もしこの要素がチェーンテーブルの最初の要素より大きい(つまり前のウィンドウの最大値より大きい)場合、私たちはチェーンテーブルを空にします(なぜチェーンテーブルを空にしたのか、そのためチェーンテーブルの中の歴史要素はこの要素ほど大きくないので、存在する価値はありません.時間が経つにつれて、ウィンドウの移動、次の要素はこの最大値と判断するだけです).
(2)この要素がチェーンテーブルの最初の要素より小さい場合は、チェーンテーブルの最後の要素より大きい場合は、チェーンテーブルの最後の要素を削除し、チェーンテーブルの最後の要素より小さいまで繰り返し操作します.(なぜそれらの小さい要素を削除するのか、新しい要素が来たので、この新しい要素が歴史の小さい要素より大きいと、時間が経つにつれて、つまりウィンドウの移動につれて、それらの歴史の小さい要素は役に立たないので、削除すればいいのです.では、なぜ列の末尾の大きい要素に出会って停止したのか、私たちは次の新しい要素が入ってきたときに確定していません.この現在値より大きい要素がウィンドウから離れているか否かを判断する3つ目の操作は、現在値より大きい要素がウィンドウから離れているか否かを判断し、ウィンドウから離れている場合、今回大きな要素が登場する)である.
(3)チェーンテーブルヘッダ要素のindexがスライドウィンドウから離れている場合、チェーンテーブルヘッダ要素を削除する.
(4)上記の3回の操作を行った後,この要素をチェーンテーブルの末尾からテーブルに入れる.
nums全体を巡回するまで、上記の4つの操作を繰り返します.
双方向チェーンテーブルは、各要素が1回または2回しか判断しないため、時間複雑度o(n)からo(2 n)の間で線形複雑度である.
次はコード(c++):
class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        vector ans;
        if(nums.size() == 0) return ans;
        list dbList;
        for(int i = 0; i < nums.size(); i++){
if(!dbList.empty()&&nums[dbList.front()]                dbList.clear();
while(!dbList.empty()&&nums[dbList.back()]                dbList.pop_back();
            if(!dbList.empty() && dbList.front()==i-k//操作三
                dbList.pop_front();
            dbList.push_back(i);
            if((i+1)>=k)
                ans.push_back(nums[dbList.front()]);
        }
        return ans;
    }
};