滑动窗口最大值：单调队列

题目

题解

遍历窗口可以考虑暴力解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


std::vector<int> maxSlidingWindow_brute(std::vector<int> &nums, int k)
{
    std::vector<int> res;
    int i, window_max;
    for (i = 0; i <= nums.size() - k; i++)
    {
        window_max = nums[i];
        for (int j = i; j < i + k; j++)
        {
            if (window_max < nums[j])
                window_max = nums[j];
        }
        res.push_back(window_max);
    }
    return res;
}

但是暴力解法在数据量大的情况下是无法接受的。

比较优秀的算法是使用单调队列的方式：

单调队列

“如果一个选手比你小还比你强，你就可以退役了。” ——单调队列原理

单调队列主要就是用来解决滑动窗口类问题的数据结构，可以做到 $O(N)$ 的时间复杂度。
其基本思想是维护一个双端队列，遍历序列，仅当一个元素可能成为某个区间最值时才保留它。

对于滑动窗口最大值问题在遍历序列主要是三步骤：

移除队尾所有小于当前值的元素
移除窗口左边界外的队头元素
窗口形成后，队头即为当前窗口的最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


std::vector<int> maxSlidingWindow(std::vector<int> &nums, int k)
{
    std::deque<int> dq;
    std::vector<int> res;
    int i;

    if (nums.empty() || k <= 0)
        return std::vector<int>{};
    for (i = 0; i < nums.size(); i++)
    {
        // 移除队尾所有小于当前值的元素
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();

        dq.push_back(i);

        // 移除窗口左边界外的队头元素
        if (dq.front() <= i - k)
            dq.pop_front();

        // 窗口形成后，队头即为当前窗口的最大值
        if (i >= k - 1)
            res.emplace_back(nums[dq.front()]);
    }
    return res;
}

题目

题解

单调队列

参考资料