Easy to understand C++ solution.


  • 0
    J

    Using deque and scan all the numbers in array:

    1, Remove all the numbers that out of window, easy to understand.

    2, Remove all the numbers that is smaller than nums[i], to keep the max number be placed in
    the front of the queue.

    3, Store the max value if needed.

    class Solution {
    public:
        
        struct ListNode{
            int v;
            int i;
        };
        
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> ans;
            deque<ListNode *> deq;
            
            for(int i = 0 ; i < nums.size() ; i++){
                
                while(!deq.empty() && deq.front()->i < i-k+1){
                    deq.pop_front();
                }
                
                while(!deq.empty() && deq.back()->v < nums[i]){
                    deq.pop_back();
                }
                
                deq.push_back(createNode(nums[i],i));
                
                if(i >= k-1) ans.push_back(deq.front()->v);
            }
            
            return ans;
        }
        
        ListNode *createNode(int v, int i){
            ListNode *node = new ListNode();
            node->v = v;
            node->i = i;
            return node;
        }
    };
    

Log in to reply
 

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