【栈与队列】滑动窗口最大值

题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

分析：首先我们可以发现滑动窗口的移动操作和队列的一进一出很相似，pop队头元素，push进队尾一个元素。所以我们可以使用队列来实现此题所需要的功能。但是题目要求返回滑动窗口的最大值，我们应该怎么做呢？大家一般第一想法就是对元素进行排序，但是排序之后我们还需要移动滑动窗口，即需要pop队头，那我们就无法pop正常需要pop的元素，每次pop的都是最大值，因此不能使用排序或者优先级队列。我们可以自己设计需要的队列让它能够找到最大值并且可以正确进行移动。

如何找到最大值，需要我们在push函数上进行设计。我们把最大值始终放在队头，把比它小的元素都pop掉。注意这里需要从back比较，并从back 进行pop，否则逻辑错误。

在pop函数设计时，由于我们有可能在push函数调用时已经pop了一些较小的元素，所以我们需要判断要pop的元素是否和队头元素相等，若相等则pop，否则说明在在push函数调用时就已经pop了，那么就不需要执行任何操作。

具体代码：

class Solution {
private:
    class Myqueue {
    public:
        deque<int> que;
        void pop(int value) {
            if(!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        void push(int value) {
            while(!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);
        }
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        Myqueue que;
        vector<int> result;
        for(int i = 0; i < k; i++) {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};