题解 | #滑动窗口的最大值# 哈希表+优先队列

#include <functional>
#include <queue>
#include <vector>
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> res;
        int n = num.size();
        // 特殊情况的处理
        if (size > n) return res;
        else if (size == 0) return res;
        // 构建一个返回最大值的优先队列
        priority_queue<int, vector<int>, less<int>> que;
        for (int i = 0; i < size; i++) {
            que.push(num[i]);
        }
        // 统计第一个结果
        res.push_back(que.top());
        // 创建一个哈希表来整理可能去除的元素
        map<int, int> mp;
        int tmp = size;
        while (tmp < n) {
            // 随着滑动窗口的更新，更新哈希表和优先队列
            if(mp.find(num[tmp-size]) == mp.end()){
                mp.insert(make_pair(num[tmp-size],1));
            }else{
                mp[num[tmp-size]] = mp[num[tmp-size]] + 1;
            }
            // for (const auto& [key, value] : mp) {
            //     std::cout << "Key: " << key << ", Value: " << value;
            // }
            cout<< endl;
            que.push(num[tmp]);
            // 检查最大值是不是落在了已经需要被排除的部分,该过程需要反复检查，直到哈希表中没有相关元素

            while (mp.find(que.top()) != mp.end() && mp[que.top()] > 0) {
                // 如果mp中找到了现在队列的最大值，则需要更新队列和mp的内容实现去除这些元素的逻辑
                // 注意这里一定要先进行mp的操作，都则que.pop()之后其top()结果将发生改变。
                mp[que.top()]--;
                que.pop();   
            }
            res.push_back(que.top());
            tmp++;
        }
        return res;
    }
};