题解 | 滑动窗口的最大值

#include <deque>
#include <queue>
class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int> ans;
        int n = num.size();
        if (size == 0 || size > n) return ans;
        deque<int> dq; // 这里用双向队列构造一个降序的队列内容（队首元素就是最大值）
        
        for (int i = 0; i < size; ++i) { // 先把前size个元素放进去
            push(dq, num[i]); // 这里使用自定义push，如果出现非降序内容会自动处理末端元素
        }
        
        ans.emplace_back(dq.front());
        for (int i = size; i < n; ++i) {
            int num_pop = num[i-size];   // 记录即将出队列的元素
            if (num_pop == dq.front()) { // 如果这个元素是队首元素，则出列
                dq.pop_front();
            }
            push(dq, num[i]); // 放入新的元素
            ans.emplace_back(dq.front());
        }
        return ans;
    }

    void push(deque<int>& dq, int k) {
        if (dq.empty() || k <= dq.back()) { // 如果队空或者队列满足降序直接插入
            dq.push_back(k);
            return;
        }
        while (!dq.empty() && dq.back() < k) { // 如果插入元素比当前队尾元素大直接不要了
            dq.pop_back();
        }
        dq.push_back(k);
    }
};