LeetCode239. 滑动窗口最大值

【题目描述】
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
【示例 1：】

 复制代码
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

【思路 优先队列】
看到找最大首先应该想到的是优先队列实现，因为这样就不需要在每一次数据加入的时候进行比较；但是，优先队列应该设计成什么样子的是个问题，起初我直接设计为priority_queue<int,vector<int>,cmp> 这导致了我在移动窗口的时候无法去除窗口外的值。 所以思考一下，由于设计为优先队列，那么去除窗口外的值一定不可能是一次移动去一个的，也不可能保证队列和窗口一样的 k 个值。

那么问题就转变为了：如果出现了去除top值后新的top值不在窗口内该如何解决？

针对这个问题，我们可以修改优先队列的设计方式，使其在值的基础上增加索引（nums中该值的位置），也就是<值，索引>的结构。当我在滑动窗口时，新的值直接进入优先队列前，队列内进行处理：如果top值在窗口内，则继续将新的值加入队列，如果top值不在窗口，则进行pop操作，直到top值在窗口为止。这样就能保证，每一次滑动时，队列内的top值一定是窗口内的值。

【C++实现代码】

 复制代码
class Solution {
public:
    struct cmp {
        bool operator()(pair<int, int> p1, pair<int, int> p2) {
            return p1.first < p2.first;
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.size() < k) return {};
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pQueue;
        vector<int> answer;
        for (int i = 0; i < nums.size(); i++) {
            // 清理优先队列中过期的元素
            while (!pQueue.empty() && pQueue.top().second <= i - k) {
                pQueue.pop();
            }
            pQueue.push({nums[i], i});
            if (i >= k - 1) {
                answer.push_back(pQueue.top().first);
            }
        }
        return answer;
    }
};