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

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
       //边界判断
        int len=num.size();
        vector<int> res;
        if(num.empty() || len<size)
            return res;
        if(size==0)
            return res;
        //双指针来固定窗口大小，同时建立大顶堆
        int start=0,end=start+size-1;
        //建立大顶堆，堆顶是最大值
        priority_queue<int>  q;
        //两个指针同时前移一位
        while(end<len)
        {
            for(int i=start;i<=end;i++)
            {
                q.push(num[i]);
            }
            //放入这个窗口的最大值
            res.push_back(q.top());
            //必须将每次的窗口全部清除
            while(!q.empty())
            {
                q.pop();
            }
            start++;
            end++;
        }
        return res;
    }
};

知识点：最大堆、双指针
针对题目，窗口值固定，则可以用双指针记录窗口边界值，同时，在每次窗口值的遍历过程中，使用优先队列。这样每次可以取队列顶部（最大值），但是记住，每次遍历串口留下的数仍然存在队列中，必须清除，以免影响下一次判断，遍历一次窗口后，窗口左右边界各向前移一位，直到到达num尾部。