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

        for(int i = 0; i < nums.size(); i++){

            //cout<<"nums[i] :"<<nums[i]<<"  "<<nums[s.back()]<<endl;
            // 如果队头下标不在窗口范围内，则从队头弹出。
            // 因为队头到队尾进入队列的顺序是从早到晚
            while(!s.empty()&&i-s.front()>=k) {
                s.pop_front();
            }
            // 如果当前元素大于等于队尾元素，则不断弹出
            while(!s.empty()&&nums[i]>=nums[s.back()]) {
                s.pop_back();
            }
            // 最后再将当前元素从队尾加入，维护一个从队头到队尾的递减队列
            // 每次队头就是每个滑动窗口的最大值所在下标。
            s.push_back(i);
            if(i>=k-1)
                res.push_back(nums[s.front()]);
        }
        return res;
    }
};