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

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> re;

        if(size==0||num.size()<size)return re;//判空

        priority_queue<int> pq;//当前窗口最大值
        priority_queue<int> pt;//已移除窗口最大值
        queue<int>q;//窗口队列

        int i=0,j=size;

        for(;i<size;i++){//初始化窗口
            pq.push(num[i]);
            q.push(num[i]);
        }


        re.push_back(pq.top());//第一个窗口最大值
        
        for(i=0;j<num.size();i++,j++){
            int tmp=q.front();
            q.pop();
            if(!pq.empty()&&pq.top()==tmp){//最大值被移出窗口
                pq.pop();
            }
            while(!pq.empty()&&!pt.empty()&&pq.top()==pt.top()){//除去不在窗口的最大值
                pq.pop();
                pt.pop();
            }
            q.push(num[j]);//移入新元素
            pq.push(num[j]);
            pt.push(num[i]);
            re.push_back(pq.top());
        }


        return re;
    }
};