【单调队列】【leetcode】【困难】239. 滑动窗口最大值

题目：

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

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

例：

输入：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

原题地址：

239. 滑动窗口最大值

解题思路1：multiset

拿到此题首先想到的是滑动窗口中位数，利用multiset，插入right，删除left，max即为最后一个数字。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        if (nums.empty() || k == 0) return ret;
        ret.reserve(nums.size() - k + 1);


        multiset<int> data;
        // 将前k个排序
        for (int i = 0; i < k; i++) data.insert(nums[i]);
        ret.push_back(*data.rbegin());
        
        for (int i = k; i < nums.size(); i++) {
            int right = nums[i];
            int left = nums[i-k];

            data.insert(right);
            multiset<int>::iterator it = data.find(left);
            data.erase(it);
            ret.push_back(*data.rbegin());
        }

        return ret;
    }
};
           

能通过（740ms）但效率不高，nlog(k)。

解题思路2：单调队列

通过翻看题解，我学到了单调队列，记录在此。

单调队列是一个单调递增或递减的队列，有几个基本操作：

• push(x)：队尾添加元素x，添加时从队尾开始向前依次找出x应该添加的位置，保证数据单调，同时删除被跳过的数据。
• pop(x)：队头元素如果是x，则删除。
• max()：返回队列最大值。

此题应用单调队列操作如下（递减单调队列）：

添加5时，比5小的数全部删除，5成为队头。

我将单调队列封装为一个类，方便后续使用，c++代码如下：

// 单调队列（Monotone Queue）：由大到小排列
class mqueue {
public:
    mqueue(int size) {
        data.reserve(size);
        left = 0;
        right = 0;
    }
    void push(int x) {
        while (right > left && data[right-1] < x) {
            --right;
        }
        data[right++] = x;
    }
    void pop(int x) {
        if (data[left] == x) left++;
    }
    int max() {
        return data[left];
    }
private:
    vector<int> data;
    // 数据范围[left, right)
    int left; // left与right相等时，数据为空
    int right;
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        if (nums.empty() || k == 0) return ret;
        ret.reserve(nums.size() - k + 1);

        mqueue q(nums.size());
        // 将前k个排序
        for (int i = 0; i < k - 1; i++) q.push(nums[i]);
        
        for (int i = k - 1; i < nums.size(); i++) {
            int right = nums[i];
            int left = nums[i-k+1];

            q.push(right);
            ret.push_back(q.max());
            q.pop(left);
        }

        return ret;
    }
};
           

运行时间260ms。时间复杂度O(N)，对于每一个数字，push一次，pop一次，整体遍历下来为O(N)。