算法数据结构

单调队列

字数统计: 3.7k字   |   阅读时长: 16分
, , , ,

摘要: 单调队列的算法原理，代码模板和应用

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

本文详细介绍单调队列的算法原理、代码模板和应用。涉及到的题目汇总如下：

$1 单调队列基本题和模板

单调队列的通用场景

在解决下面这类问题时，单调队列是一个有力的数据结构：

对每个 0 <= j <= n - 1，摊销 $O(1)$ 地求 [i..j] 上的最值以及其对应的下标。这正是单调队列的模板题，如下：

求 [i, j] 上的最值及其下标的过程中，有时在 0 <= i <= j 的基础上，i 需要满足某些条件，当不满足时 i 需要递增。例如：

  • [i, j] 上的最值需要满足某些条件：例如后面的问题1~2；
  • [i, j] 的区间长度要满足某些条件：滑动窗口最大值，例如后面的问题3。

问题1：两个数组 a, b, 长度均为 N。求有多少个区间 [l, r]，使得在区间 [l, r] 上 a 的最大值小于 b 的最小值。

问题2：对应问题1中满足条件的区间 [l, r]，找到长度最大的区间，返回区间长度最大值和 a 在该区间上的最大值

问题1和2的思路如下：

用两个单调队列维护当前最值，一个保存 a 上最大值的递减队列 deq1，一个保存 b 上最小值的递增队列 deq2，如果目前 a 上最大值 a[deq1.front()] 大于等于 b 上最小值 b[deq.front()]，要出队，只出队下标小的，出队后更新当前区间。

问题3：求最大子串和(前缀和上的单调队列)

问题3的思路参考文章 最大子数组和的三种解法。

代码模板 (基本模型：滑动窗口最大值)

这里给出单调队列的模板题 239. 滑动窗口最大值 的代码模板。

详细的题解看文章 力扣239-单调队列,索引堆。

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
27
28
29
30
31
32
33
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;
}

变种：不固定长度的滑动窗口最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

限制：

1
2
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 1e5

示例 1：
输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：
输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]

算法：单调队列

窗口 [i, j] 向右推进，但推进 i 还是推进 j 未知。

  • 数据队列 queue<int> 维护 [i, j] 内的数据
  • 窗口队列 deque<int> 维护 [i, j] 上的最大值单调队列

代码 (C++)

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
27
28
29
30
31
32
class MaxQueue {
public:
    MaxQueue() {
        q = queue<int>();
        mq = deque<int>();
    }

    int max_value() {
        if(q.empty()) return -1;
        return mq.front();
    }

    void push_back(int value) {
        q.push(value);
        while(!mq.empty() && mq.back() < value)
            mq.pop_back();
        mq.push_back(value);
    }

    int pop_front() {
        if(q.empty()) return -1;
        int ans = q.front();
        q.pop();
        if(!mq.empty() && mq.front() == ans)
            mq.pop_front();
        return ans;
    }

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

$2 区间长度限制队内下标

(1) 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

提示：

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

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

算法：前缀和+单调队列

下面是单调队列解决本题的思路和代码，其它解法看文章 力扣53,918-Kadane算法。

1
2
a[0..i] 的和 sums[i+1] 求出后
问 sums[0..i] 的最小值是多少

这里问最值的区间左端点是没有限制的，一直是 0，当新下标 i 来的时候，只会在队尾弹出一些比 sums[i] 小的，而不会因为区间的限制从左边弹出下标。

这种不用从左边弹出下标的场景用单调队列有点多此一举，不过后面的限制子段长度的最大子段和就需要用到单调队列的从左边弹出不满足区间限制的下标这个特性了。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n + 1, 0);
        deque<int> deq;
        deq.push_back(0); // sums[0] = 0
        int ans = INT_MIN;
        for(int i = 0; i < n; ++i)
        {
            sums[i + 1] = sums[i] + nums[i];
            // 此时问：sums[0..i] 上的最小值 mx 是多少
            // ans = max(ans, sums[i + 1] - mx)
            int  mx = sums[deq.front()];
            ans = max(ans, sums[i + 1] - mx);
            while(!deq.empty() && sums[deq.back()] >= sums[i + 1])
                deq.pop_back();
            deq.push_back(i + 1);
        }
        return ans;
    }
};

(2) 限制子段长度的最大子段和

输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 1。

1
2
3
4
5
6
7
8
9
10
输入格式
第一行输入两个整数 n,m。
第二行输入 n 个数，代表长度为 n 的整数序列。
同一行数之间用空格隔开。

输出格式
输出一个整数，代表该序列的最大子序和。

数据范围
1<=n,m<=300000

输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7

算法：前缀和+单调队列

限制子段长度不超过 m

1
2
3
a[0..i] 的和 sums[i+1] 求出后
问 sums[max(0, i - m + 1)..i] 的最小值是多少
查询长 <= m，的子段和，对应的要维护长度 <= m + 1 的前缀和

代码 (C++)

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
27
28
29
30
31
#include <iostream>
#include <vector>
#include <deque>
#include <climits>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> sums(n + 1);
    deque<int> deq;
    deq.push_back(0);
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        int v;
        cin >> v;
        sums[i + 1] = sums[i] + v;
        int mx = sums[deq.front()];
        ans = max(ans, sums[i + 1] - mx);
        while(!deq.empty() && sums[deq.back()] >= sums[i + 1])
            deq.pop_back();
        deq.push_back(i + 1);
        // i - (deq.front() - 1) + 1 <= m
        if(i - (deq.front() - 1) + 1 > m)
            deq.pop_front();
    }
    cout << ans << endl;
}

(3) 限制子序列长度的最大子序列和

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

提示：

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

示例 1：
输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：
输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：
输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

算法：单调队列优化 DP

1
2
3
dp[i] := [0..i] 且以 i 为终点的最大子序列和
max(dp[i]) 为答案
初始化  dp[0] = nums[0]

转移：

在求 dp[i] 时，问：i 左侧长度最大为 K 的窗口中，dp 的最大值是多少。

此时 deq 中维护的是 dp[max(0, i - K + 1) .. i - 1] 的单调递减队列。

详细题解参考文章 单调队列优化DP。

代码 (C++)

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
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        int K = k + 1; // 窗长 K
        vector<int> dp(n);
        dp[0] = nums[0];
        deque<int> deq;
        deq.push_back(0);
        int ans = dp[0];
        for(int i = 1; i < n; ++i)
        {
            int mx = dp[deq.front()];
            dp[i] = nums[i] + max(0, mx);
            ans = max(ans, dp[i]);
            while(!deq.empty() && dp[deq.back()] <= dp[i])
                deq.pop_back();
            deq.push_back(i);
            // 队列中维护 [i - K + 2, i]  长度为 K - 1
            if(deq.front() <= i - K + 1)
                deq.pop_front();
        }
        return ans;
    }
};

$3 最值大小限制队内下标

一般单调队列对 deq 中的下标有一定限制，例如通过区间长度限制等。这里是对下标对应的值有一定限制。

(1) 子段和满足一定范围的最短子段

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

提示：

1
2
3
1 <= nums.length <= 1e5
-1e5 <= nums[i] <= 1e5
1 <= k <= 1e9

示例 1：
输入：nums = [1], k = 1
输出：1

示例 2：
输入：nums = [1,2], k = 4
输出：-1

示例 3：
输入：nums = [2,-1,2], k = 3
输出：3

算法：前缀和+单调队列

1
2
3
4
5
6
7
8
9
10
11
12
sums[i + 1] := [0..i] 的前缀和
在 deq 中维护 sums 的单调递增队列

枚举 i(1,2 ..., n)
    求当前的前缀和 sums[i]
    此时队列中维护的是 `sums[deq.back()] - sums[deq.front()] < K` 的下标
    若 s[i] - s[dq.front()] >= K，则:
        更新答案 ans = min(ans, i - deq.front())
        更新完答案后 deq.front() 弹出
    将 i 从队尾压队之前，需要从队尾弹出一些不满足单调性的元素
    while(!deq.empty() && sums[deq.back()] >= sums[i])
        deq.pop_back();

代码 (C++)

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
27
28
29
30
class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size();
        vector<int> sums(n + 1, 0);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + A[i - 1];
        deque<int> deq; // deq 中存 sums 的下标
        deq.push_back(0); // 前缀和的0
        int result = n + 1;
        for(int i = 1; i <= n; ++i)
        {
            // 先更新队头的答案, 若满足下式则可以更新答案
            // s[deq.front()] + K <= s[i]
            while(!deq.empty() && sums[deq.front()] + K <= sums[i])
            {
                result = min(result, i - deq.front());
                deq.pop_front();
            }

            // 然后 i 进队之前先看有没有可以弹出的
            while(!deq.empty() && sums[deq.back()] >= sums[i])
                deq.pop_back();

            deq.push_back(i);
        }
        if(result == n + 1) return -1;
        return result;
    }
};

(2) 子段极差满足一定范围的最长子段

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。

示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

提示：

1
2
3
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9
0 <= limit <= 1e9

算法：单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
deq1 维护区间最大值, 单调增
deq2 维护区间最小值, 单调减

推进 i 的时候，维护一个 left，表示当前不违反极差限制的区间左端点

当前枚举 i:
    此时 deq1, deq2 中维护的是 [left, i - 1] 中的下标序列，[left, i - 1] 不违反极差限制
    nums[i] 可能会打破极差限制:
        (1) abs(nums[deq1.front()] - nums[i]) > limit
        (2) abs(nums[deq2.front()] - nums[i]) > limit
        将这些违反极差限制的下标从队头弹出
        每弹出一个 front，更新 left = front + 1
    将被 i 打破极差限制的下标弹出并更新 left 之后，更新答案 ans = max(ans, i - left + 1)
    将队尾不满足单调性的下标弹出
    将 i 压队

代码 (C++)

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
27
28
29
30
31
32
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        deque<int> deq1, deq2;
        deq1.push_back(0);
        deq2.push_back(0);
        int ans = 1;
        int left = 0;
        for(int i = 1; i < n; ++i)
        {
            while(!deq1.empty() && abs(nums[deq1.front()] - nums[i]) > limit)
            {
                left = deq1.front() + 1;
                deq1.pop_front();
            }
            while(!deq2.empty() && abs(nums[deq2.front()] - nums[i]) > limit)
            {
                left = deq2.front() + 1;
                deq2.pop_front();
            }
            ans = max(ans, i - left + 1);
            while(!deq1.empty() && nums[deq1.back()] < nums[i])
                deq1.pop_back();
            while(!deq2.empty() && nums[deq2.back()] > nums[i])
                deq2.pop_back();
            deq1.push_back(i);
            deq2.push_back(i);
        }
        return ans;
    }
};
Share