题解 | #滑动窗口的最大值#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @param size int整型
     * @return int整型vector
     */
    //定义一个单调队列，队列中始终维护出口处为最大值，且新加入的元素始终是有希望成为最大值
    class monotony_queue {
      public:
        deque<int> que; // 使用deque来实现单调队列
        void pop(int val){
		  //如果要弹的元素刚好是队列出口，直接出，否则就说明在以前Push元素的时候已经弹出
            if (!que.empty() && val==que.front()) {
                que.pop_front();
            }
        }
        void push(int val) {
            while (!que.empty() && que.back() < val) {
                que.pop_back();
            }
            que.push_back(val);
        }
        int get_maxvalue() {
            return que.front();
        }
    };

    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int>result;
        if (size == 0 || size > num.size()) {
            return result;
        } else if (num.size() == 1) {
            result.push_back(num[0]);
            return result;
        }
        monotony_queue myque; 
        for (int i = 0; i < size; i++) {
            myque.push(num[i]);
        }
        //记录第一个窗口最大值
        result.push_back(myque.get_maxvalue());
        //第二个窗口以后都是先弹前面再入后面
        for (int i=size; i<num.size(); i++) {
            myque.pop(num[i-size]);
            myque.push(num[i]);
            result.push_back(myque.get_maxvalue());
        }
        return result;
    }

};