剑指59：滑动窗口的最大值

传送门

nowcoder
leetcode

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5}。
窗口大于数组长度或窗口长度为0的时候，返回空。

C++ 代码 - nowcoder

/*
    单调栈：使用双端队列
*/
class Solution {
  public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        if (size <= 0 || num.size() == 0 || num.size() < size) return {};

        vector<int> res;
        int length = num.size();
        deque<int> dq; // 存储 num 的下标
        for (int i = 0; i < length; i ++) {
            // 若当前值比队列从后往前的大，则为下一个待选值
            while (!dq.empty() && num[dq.back()] < num[i]) {
                dq.pop_back();
            }
            // 最大值已不在窗口中
            while (!dq.empty() && i - dq.front() + 1 > size) {
                dq.pop_front();
            }
            dq.push_back(i);
            // 若滑动窗口首地址 i >= size 时，则写入窗口最大值
            if (i + 1 >= size) {
                res.push_back(num[dq.front()]);
            }
        }
        
        return res;
    }
};

/*
    使用优先队列
*/
class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        if (size <= 0 || num.size() == 0 || num.size() < size) return {};

        vector<int> res;
        int length = num.size(), count = 0;
        priority_queue<int> pq; // 默认是大顶堆
        for (int i = 0; i <= length - size; i ++) {
            while (count < size) {
                pq.push(num[i + count]);
                count ++;
            }
            count = 0;
            res.push_back(pq.top());
            while (!pq.empty()) {
                pq.pop();
            }
        }

        return res;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    vector<int> maxAltitude(vector<int>& nums, int k) {
        MonotonicQueue window;
        vector<int> res;

        for (int i = 0; i < nums.size(); i++) {
            if (i < k - 1) {
                // 填满窗口的前 k - 1
                window.push(nums[i]);
            } else {
                // 窗口向前滑动，加入新数字
                window.push(nums[i]);
                // 记录当前窗口的最大值
                res.push_back(window.max());
                // 移出旧数字
                window.pop(nums[i - k + 1]);
            }
        }
        return res;
    }

private:
    /* 单调队列的实现 */
    class MonotonicQueue {
    public:
        void push(int n) {
            // 将小于 n 的元素全部删除
            while (!q.empty() && q.back() < n) {
                q.pop_back();
            }
            // 然后将 n 加入尾部
            q.push_back(n);
        }

        void pop(int n) {
            if (n == q.front()) {
                q.pop_front();
            }
        }

        int max() {
            return q.front();
        }

    private:
        deque<int> q;
    };
};