超级重点题，感觉很经常考。

法1：优先队列
用一个存储值和数组索引的pair放在优先队列里，当索引超出窗口范围，就把优先队列里的值删掉。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < k; i++){
            q.push({nums[i], i});
        }
        vector<int> res;
        res.emplace_back(q.top().first);

        for(int i = k; i < nums.size(); i++){
            q.push({nums[i], i});
            // 我们只关心滑动窗口的最大值 因此只需要保证q.top中的值满足在窗口中就行了
            while(q.top().second <= i - k){
                q.pop();
            }
            res.emplace_back(q.top().first);
        }
        return res;
    }
};

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。

空间复杂度：O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间，只计算额外的空间使用。

法2：单调队列
使用一个双端队列来维护滑动窗口内的元素索引，使得队列的首元素始终是当前窗口的最大值的索引。 单调队列的核心是维护一个严格递减的队列

具体来说，对每个元素进行以下操作：

• 移除队列中不在当前窗口范围内的元素（即索引过期的元素）。
• 移除队列中所有比当前元素小的元素，因为它们不可能再成为最大值。
• 将当前元素的索引添加到队列中。
• 队列的首元素即为当前窗口的最大值，将其添加到结果数组中。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        for(int i = 0; i < k; ++i){
            // 维护严格递减的队列 如果当前的值比队尾的大 就把队尾扔了 注意维护的是下标
            while(!dq.empty() && nums[i] >= nums[dq.back()]){
                dq.pop_back();
            }
            dq.push_back(i);
        }
        // 维护后的队列 一定是队首的值代表这个窗口的最大值
        vector<int> res;
        res.push_back(nums[dq.front()]);
        for(int i = k; i < nums.size(); ++i){
            while(!dq.empty() && nums[i] >= nums[dq.back()]){
                dq.pop_back();
            }
            dq.push_back(i);
            // 判断最大的值 是否还在窗口内 不在就要pop掉
            while(dq.front() <= i - k){
                dq.pop_front();
            }
            res.push_back(nums[dq.front()]);
        }
        return res;
    }
};