【leetcode】239. 滑动窗口最大值（单调队列）

https://leetcode-cn.com/problems/sliding-window-maximum/

解题思路：
https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/dan-tiao-dui-lie

class MonotonicQueue
{
private:
	deque<int> data; // 单调队列中元素的个数不一定非要恒等于k
public:

	// 比它小的都pop出去，保持队列的头部为最大
	void push(int val)
	{
		while (!data.empty() && data.back() < val)
			data.pop_back();

		data.push_back(val);
	}

	// 队列的头或者尾部
	int max()
	{
		return data.front();
	}

	// pop出去早先在队列里添加的元素
	void pop(int val)
	{
		// 这里不能while循环，否则重复的元素就出问题了
		if (!data.empty() && data.front() == val)  
			data.pop_front();
	}

};

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


        vector<int> res(nums.size() - k + 1);
        MonotonicQueue* que = new MonotonicQueue();

        for (int i = 0; i < nums.size(); i++)
        {
            if (i < k - 1)
            {
                que->push(nums[i]);
            }
            else
            {
                que->push(nums[i]);
                res[i - k + 1] = que->max();
                que->pop(nums[i - k + 1]);
            }
        }

        return res;
    }
};