题解 | #滑动窗口的最大值——优先队列+延迟删除#

优先队列可以快速知道哪个值最大，但是不支持移除某一个元素。所以采用hashmap记录待删除的元素，当它到达栈顶的时候再检查是否为要删除的元素，顺势弹走。滑动窗口里取最大值、中位数等都是一样的。

class DualHeap {
private:
    // 大根堆
    priority_queue<int> small;

    // 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
    unordered_map<int, int> delayed;

    int k;

public:
    DualHeap(int _k): k(_k) {}

    void insert(int num) {
        small.push(num);
    }

    void erase(int num) {
        ++delayed[num];
    }

    int getMax() {
        while (!small.empty()) {
            int num = small.top();
            if (delayed.count(num)) {
                --delayed[num];
                if (!delayed[num]) {
                    delayed.erase(num);
                }
                small.pop();
            }
            else {
                break;
            }
        }
        return small.top();
    }
};

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& nums, int k) {
        DualHeap dh(k);
        for (int i = 0; i < k; ++i) {
            dh.insert(nums[i]);
        }
        vector<int> ans = {dh.getMax()};
        for (int i = k; i < nums.size(); ++i) {
            dh.insert(nums[i]);
            dh.erase(nums[i - k]);
            ans.push_back(dh.getMax());
        }
        return ans;
    }
};