Leetcode 239. Maximum sliding window

subject

  Give you an array of integers nums, There is a size of k The sliding window of the array moves from the leftmost side to the rightmost side of the array . You can only see... In the sliding window k A digital . The sliding window moves only one bit to the right at a time . return The maximum value in the sliding window .

Ideas

 Refer to the explanation of the question ：https://leetcode.cn/problems/sliding-window-maximum/solution/tu-jie-suan-fa-dan-diao-dui-lie-zui-jian-h012/

Code

class Solution {
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        deque<int> q;//  deque 
        vector<int>res;

        for(int i = 0; i < nums.size(); i++)
        {
    
            while(q.size() && i - k + 1 > q.front())
            {
    
                q.pop_front();//  Judge whether the counterpart is within the sliding window range 
            }
            while(q.size() && nums[i] >= nums[q.back()])
            {
    
                //  The current element is larger than the tail element 
                q.pop_back();//  Maintain monotonic decreasing queues 
            }
            q.push_back(i);//  Insert the current element at the end of the queue 

            if(i >= k - 1)
            {
    
                res.push_back(nums[q.front()]);//  The element of the sliding window has reached k individual   Insert the header element into the result array 
            }
        }

        return res;
    }
};