滑动窗口中的最大值 (Sliding Window Maximum / Monotonic Queue)

Leetcode 上有一道题叫 Sliding Window Maximum，虽然不是今天刷的，但是解法非常有意思，就记录一下。

问题描述：

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the max sliding window as [3,3,5,5,6,7].

这道题可以用优先队列、自平衡 BST 等方法得到一个 O(nlgn) 的解法，但其实这道题有另一种 O(n) 的解法，基本思想是在过程中维持一个单调队列。

Monotonic Queue#

我们用双端队列来实现这个单调队列，保证这个队列中所有数单调非增，同时一个窗口中的最大的数就在队列的开端。

假设我们现在有一个队列 Q 满足上述条件，当一个数 a 进入窗口时，此时数 b 滑出窗口，队列操作步骤：

如果队列不为空并且队列开端等于 b，remove it!
如果队列不为空并且队列尾端小于 a，remove it！
循环 步骤 2 直到队列为空或者队列尾端不小于 a
将 a 加到队列尾端

显然，在 步骤 2 中，删除的数都是不可能为最大值的数，所以在操作结束后，窗口内最大值仍然在队列中，并且队列保持单调非增。

此时最大值即为队列开端。

因为每个数只进队一次，并出队一次，所以时间开销为 O(n)。

Appendix#

C++ 实现#

1
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
2
    vector<int> res;
3
    // tracking index instead of value
4
    deque<int> dq;
5

6
    for (int i = 0; i < nums.size(); ++ i) {
7
        // dequeue (i - k)th element if exists
8
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();
9
        // remove those less than current
10
        while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
11
        // enqueue current
12
        dq.push_back(i);
13

14
        if (i >= k - 1) res.push_back(nums[dq.front()]);
15
    }
16

17
    return res;
18
}