2020-04-06 刷题1（队列）

滑动窗口的最大值

用一个双向队列（两边都开口）deque来存放滑动窗口中可能成为最大值的下标，每读到一个新的数时，如果队列中存在比它小的元素，那么这些元素都不可能成为最大值了，因此，把这些元素从右边出队列；当前元素从右边入队列。因此，队列中的元素总是从左到右递减的，每次要取的窗口最大值就是最列前端。当元素已经超出滑动窗口范围时，根据队列中存放的下标与当前窗口位置的距离，就可以判断出来并且将其出队列。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> my_queue;
        vector<int> max_window;
        if(nums.size() < k) return max_window;
        for(int i = 0; i < nums.size(); i++){
            if(my_queue.size() == k) my_queue.pop_front();
            while(!my_queue.empty() && nums[my_queue.back()] <= nums[i])
                my_queue.pop_back();
            if(!my_queue.empty() && i - my_queue.front() >= k) my_queue.pop_front();
            my_queue.push_back(i);
            if(i >= k - 1)
                max_window.push_back(nums[my_queue.front()]);
        }
        return max_window;
    }
};