C++优先队列 emplace方法 & lc239

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 优先队列做法 复杂度nlogn
        // emplace可以直接生成元素插入到优先队列中去

        /*priority_queue<pair<int,int>> pq;//优先队列，大顶堆，以第一个元素作为key排序
        for(int i = 0; i < k; ++i) pq.emplace(nums[i],i);//把前k个元素加入
        vector<int> res = {pq.top().first};//保存好第一个滑动窗口的答案
        for(int i = k; i < nums.size(); ++i) { //滑动窗口向后移动
            pq.emplace(nums[i], i);//新加入一个元素
            while(pq.top().second + k <= i) pq.pop();//判断当前最大的元素是否不在滑动窗口中，找到一个最大&在窗口中的
            res.push_back(pq.top().first);//保存答案
        }
        return res;*/



        // acwing做法 复杂度n
        // 思考一下hint的做法，使用双端队列
        // 双端队列的长度不等于k，只要考虑应该考虑的元素，而移除多余的元素
        // 实际上就是一个单调双端队列
        // 暴力+优化：删掉所有不可能成为答案的元素之后，惊奇的发现，这竟然是一个单调队列

        deque<int> q;//单调双端队列记录下标
        vector<int> res;
        for(int i = 0; i < nums.size(); ++i) {
            while(q.size() && i - k + 1 > q.front()) q.pop_front();
            while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;


    }
};