C++ solution with deque. O(n) time. easy understand


  • 0
    W

    1,In every steps, we pop some numbers out of the deque and push a number into the deque.

    2,The most important part is, every number in the deque which is smaller than the number that needed to be push into the deque is useless.

    3,we can delete numbers which is smaller then the new number from both the front and the end of the queue, Then push the new number to the back of the queue.

    struct item{
        int pos,val;
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<item> que;
        vector<int> res;
        item temp;
        for(int i = 0,j = 0;i < nums.size() && j < nums.size();++ i){
            //if the position of a number in the deque is smaller the i, we should delete it
            if(!que.empty() && que.front().pos < i) que.pop_front();
            for(;j < nums.size() && j < i + k;++ j){
                temp.pos = j;
                temp.val = nums[j];
                //delete numbers from dequeue
                while(!que.empty() && que.front().val <= temp.val) que.pop_front();
                while(!que.empty() && que.back().val <= temp.val) que.pop_back();
                que.push_back(temp);
            }
            res.push_back(que.front().val);
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.