LeetCode 239. 滑动窗口最大值

做的第一个困难的题。
这题一上来很容易想到挨个求窗口的最大值来解决，但是那样会超时
正确解法是利用双队列来实现一个单调队列，只保存最大值和可能大的值

class Solution {
public:
    class MyQueue{
    public:
        deque<int> que;
        void push(int x)
        {
        	//实现单调队列只保存最大值和可能最大的值
            while((!que.empty()) && x > que.back())
            {
                que.pop_back();
            }
            que.push_back(x);
        }
        void pop(int x)
        {
            if(que.front() == x)
                que.pop_front();
        }
        int front()
        {
            return que.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;
        for(int i = 0; i < k; i++)
            que.push(nums[i]);
        res.push_back(que.front());

        for(int i = k; i < nums.size(); i++)
        {
            que.push(nums[i]);
            que.pop(nums[i - k]);
            res.push_back(que.front());
        }
        return res;
    }
};