LeetCode刷题 - 滑动窗口最大值

参考链接:https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

leetcode题目链接：https://leetcode.cn/problems/sliding-window-maximum/

给你一个整数数组 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

示例 2：

输入：nums = [1], k = 1 输出：[1]

方法1：单调队列法

使用一个数据结构，每次滑动窗口时添加一个元素，删除一个元素，同时可以从队列头部获取想要的当前窗口内的最大值。这种数据结构就是单调队列，单调队列的pop和push操作应该遵循以下原则：

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么弹出元素，否则不需要任何操作；
2. push(value)：如果push的元素value大于入口元素的值，那么将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。
   基于如上规则，每次窗口移动后，队列头部元素就是当前窗口的最大值。

class MyQueue { //单调队列（从大到小）
public:
    deque<int> que; // 使用deque来实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);

    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return que.front();
    }
};

方法2：优先级队列

使用大顶堆，每次移动窗口时，将新的元素加入堆中，此时需要移除堆中不在窗口内的元素。为了记录堆中元素是否在窗口中，需要记录堆中元素在数组中的索引。在每次获取当前窗口内最大值之前，将堆顶的索引不在当前窗口内的元素移除。具体的实现方式如下：

class Solution {
    struct Node {
        int num;
        int idx;
        Node(int n, int i) : num(n), idx(i) {}
        bool operator < (const Node& b) const {
            return this->num != b.num ? (this->num < b.num) : (this->idx < b.idx);
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<Node> pq;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            pq.push(Node(nums[i], i));
            if (i >= k-1) {
                while (pq.top().idx <= i - k) {
                    pq.pop();
                }
                res.push_back(pq.top().num);
            }
        }
        return res;
    }
};