滑动窗口最大值

堆和双向队列

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

这道题有两种解法，一种是使用大顶堆，一种是使用双向队列

方法一：

使用大顶堆，维护一个长度为k的大顶堆，存放的每个元素为一个数对，分别为数值和下标，每次加入新元素，然后把超出窗口的元素删除，怎么算超出窗口呢，也就是下表位于窗口左边界左侧的，如果当前下标为i，那么左边界就是i-k+1。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

方法二：

使用一个双向链表，右边入队出队，左边出队排除过期的元素，同时存放的每个元素也是一个数对，分别为数值和下标。对于一个新元素，如果大于队尾，则出队，直到队尾元素小于当前元素，当前元素入队。同时排除掉队头超过窗口边界的元素，下标不符合范围的出队

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};