力扣239-滑动窗口最大值

摘要: 非常经典的题目：滑动窗口最大值，有单调队列、平衡树、堆等解法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们来看一个经典题，滑动窗口最大值。主流方法有两类，一类是基于单调队列的方法，一类是基于在堆上加索引的方法，当然也可以用平衡树，这应该算是第二类方法。

$1 题目

• 239. 滑动窗口最大值

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

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

提示：

1 <= nums.length <= 1e5
-1e4 <= nums[i] <= 1e4
1 <= k <= nums.length

示例:
输入: 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 题解

算法1：单调队列

单调队列的 $O(N)$ 是本题的最好解法。算法原理参考文章 单调队列。

不定长区间最值问题是著名的RMQ问题，主流解法有线段树，稀疏表等，每次查询都是摊销 $O(\log N)$ 的。如果区间长度固定，用单调队列可以优化到每次查询摊销 $O(1)$。

单调队列的核心使用场景：长度固定的区间最值问题

维护一个 保存下标的 deque (与索引堆的思想类似)。队头始终是当前区间的最大值对应的下标。

枚举当前下标 j ，队头是以 j 为右端点的区间的最大值对应的下标。更新 j 对应的答案后，需要将 j 压进队，在此之前可能需要从队尾弹出一些值：如果队尾对应的值小于等于当前值，即 nums[deq.back()] <= nums[j] ， 则把队尾弹出，直至队尾对应的值大于当前值或队列空了，再将 j 压入，这是因为当 i1 < i2 时， nums[i1] <= nums[i2]，则 i1 不会是后续下标 j 的答案了，因为 i2 总是比 i1 要好(有 i2 在，nums[i1] 就不会是最大值)。队列中始终保持单调递减。

当队头与当前枚举的右端点 j 的距离大于窗口长度了，则队头不可能是后续右端点的答案，需要将其从队头弹出。

代码(c++)

本题可以作为单调队列的模板题，以下代码可以作为模板代码。

class Solution_2 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        if(n <= k)
        {
            int mx = nums[0];
            for(int i = 1; i < n; ++i)
                mx = max(mx, nums[i]);
            return vector<int>({mx});
        }
        // 滑动 n - k 次
        // 0..k-1
        deque<int> dq;
        vector<int> result;
        for(int i = 0; i < k; ++i)
        {
            // 插入 i 前先出队
            while(!dq.empty() && nums[dq.back()] <= nums[i])
                dq.pop_back();
            dq.push_back(i);
        }
        result.push_back(nums[dq.front()]);
        for(int i = k; i < n; ++i)
        {
            if(!dq.empty() && dq.front() <= i - k) 
                dq.pop_front();
            while(!dq.empty() && nums[dq.back()] <= nums[i])
                dq.pop_back();
            dq.push_back(i);
            result.push_back(nums[dq.front()]);
        }
        return result;
    }
};

算法2：平衡树 (multiset)

平衡树维护滑动窗口内的值。STL可以直接用的设施：multiset。

平衡树的最后一个节点始终是树中最大的值，对应到 multiset 的接口：

*(setting.rbegin());

先把 [0..k-1] 的数插入平衡树内。

然后枚举 k <= i <= n-1 ，先把 nums[i - k] 从平衡树中删掉 $O(\log N)$。然后插入 nums[i] $O(\log N)$，当前树中的最大值 $O(\log N)$ 就是区间 [i - k + 1, i] 上的最大值。

代码(C++)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        if(n <= k)
        {
            int mx = nums[0];
            for(int i = 1; i < n; ++i)
                mx = max(mx, nums[i]);
            return vector<int>({mx});
        }
        // 滑动 n - k 次
        // 0..k-1
        multiset<int> setting;
        vector<int> result;
        for(int i = 0; i < k; ++i)
            setting.insert(nums[i]);
        result.push_back(*(setting.rbegin()));
        for(int i = k; i < n; ++i)
        {
            setting.erase(setting.find(nums[i - k]));
            setting.insert(nums[i]);
            result.push_back(*setting.rbegin());
        }
        return result;
    }
};

算法3：索引堆

使用索引堆的时间复杂度为 $O(N\log N)$，不是最优解且很难写，并且比较依赖优化，仅作参考。

加索引有很多种方法，也有优化的问题，下面是以下标索引堆为例简要说明，更详细的原理参考文章 下标索引堆。

动态最值问题最直观的做法：维护一个容量为 k 的最大堆，每次窗口右移一位时，将移动之前窗口最左端的值从堆中弹出，移动后将窗口最右端的值压入，此时堆顶是当前窗口的答案。

问题：将移动之前窗口最左端的值从堆中弹出这一步需要将非堆顶元素删除。这需要知道被删元素在堆数据数组中的位置，但是在此前的插入删除时维持堆性质的 push_up 和 push_down 操作时，元素在对数组中的初始位置已经打乱。

需要有一种办法使得数据在为了维持需要的性质而改变位置后，还能知道它在数组中的位置。索引堆的意思就是堆中保存数据的原始数组 heap 在插入之后就不变了，在 push_up 和 push_down 的过程中，改变的是原始数组 heap 的索引数组 indexes，普通的堆是 heap[i] 保持堆的性质，索引堆是 heap[indexes[i]] 保持堆的性质。索引堆内部使用了索引数组的思想： 线性索引表。

索引堆的插入删除需要带着索引 index。因为窗口长度固定是 k。所以每个删除都对应一个插入，所以每次需要将 i 位置的值删除时，带着删除后要插入的值 x，直接把 i 位置的值改成 x，可以将删除和插入合成一步。

void insert(int index, int x)
void change(int index, int x)

insert 和 change 传入的 index = i % k 是堆中原始数据数组的索引，其中 i 为 nums 对应的下标。在 push_up 和 push_down 中，为保持堆性质要改变的是 indexes 数组，所以需要有一个查找表 reverses 保存从原始数组 heap 的下标到索引数组 indexes 的下标的映射。

vector<int> heap;
vector<int> indexes;
vector<int> reverses;

代码(c++)

class MaxIndexHeap {
public:
    MaxIndexHeap(int n) {
        heap = vector<int>(n + 1, 0); // 数据数组 heap 从 1 开始
        indexes = vector<int>(n + 1, 0); // 索引数组 从 1 开始
        reverses = vector<int>(n + 1, 0); // 反向查找表 从 1 开始
        count = 0;
    }

    int top() {
        return heap[indexes[1]];
    }

    void insert(int index, int x){ // push 改为 insert，既然用索引堆则插入必须带索引
        if(contain(index)) return; // 若index这个位置已经有值，则无动作
        // 若该位置以前有值，但后来被删除了，则该位置又可以插入了
        heap[index + 1] = x;
        indexes[count + 1] = index + 1;
        reverses[index + 1] = count + 1;
        ++count;
        _push_up(count);
    }

    void change(int index, int x) {
        // 索引堆多出来的关键功能
        heap[index + 1] = x;
        _push_up(reverses[index + 1]);
        _push_down(reverses[index + 1]);
    }

    bool contain(int index) {
        return reverses[index + 1] != 0;
    }

private:
    vector<int> heap;
    vector<int> indexes;
    vector<int> reverses;
    int count;

    int _size() {
        return count;
    }

    // 堆的元素下标从1开始
    void _push_down(int u)
    {
        int size = _size();
        if(u > size) return;
        int t = u, left = u * 2, right = u * 2 + 1;
        if(left <= size && heap[indexes[left]] > heap[indexes[t]]) t = left;
        if(right <= size && heap[indexes[right]] > heap[indexes[t]]) t = right;
        if(t != u)
        {
            swap(indexes[u], indexes[t]);
            reverses[indexes[u]] = u;
            reverses[indexes[t]] = t;
            _push_down(t);
        }
    }

    void _push_up(int u)
    {
        int size = _size();
        if(u > size) return;
        while(u / 2 && heap[indexes[u / 2]] < heap[indexes[u]])
        {
            swap(indexes[u / 2], indexes[u]);
            reverses[indexes[u]] = u;
            reverses[indexes[u / 2]] = u / 2;
            u /= 2;
        }
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        if(n <= k)
        {
            int mx = nums[0];
            for(int i = 1; i < n; ++i)
                mx = max(mx, nums[i]);
            return vector<int>({mx});
        }
        // 滑动 n - k 次
        // 0..k-1
        MaxIndexHeap heap(k);
        vector<int> result;
        for(int i = 0; i < k; ++i)
            heap.insert(i, nums[i]);
        result.push_back(heap.top());
        for(int i = k; i < n; ++i)
        {
            heap.change(i % k, nums[i]);
            result.push_back(heap.top());
        }
        return result;
    }
};

---