详解单调队列算法

大家好，又见面了，我是你们的朋友全栈君。

前言 嘿！彩蛋！感觉有帮助就三连呗！

如果你对这篇文章可感兴趣，可以点击「【访客必读 – 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

在上一篇文章中，我们介绍了「单调栈」这一最常考察的线性数据结构。而今天我们将继续沿着这个思路，介绍另一个与其 “齐名” 的线性数据结构，即「单调队列」。

「单调队列」在「数据结构」题中的分布较为广泛，且常被当作优化「动态规划」的一种重要手段，因此该算法在面试中考察的频率较高，属于必知必会的知识点。

队列

首先我们来回忆一下「队列」。「队列」是一种「先进先出」的线性数据结构，其中元素只能从队尾进，从队首出。

如下图所示，3 1 4 5 2 7 依次入队又依次出队，其结果满足「先进先出」的要求。另外，有标记的位置分别代表队首与队尾，其中左边为队首。

单调队列

回忆完「队列」后，我们开始「单调队列」的讲解。

什么是「单调队列」？顾名思义，「单调队列」就是队列内元素满足单调性的队列结构。且为了满足队列内元素的单调性，队尾也可弹出元素。此处的单调性分为单调递增与单调递减，为了便于描述，接下来以「单调递增队列」为例进行讲解。

「单调递增队列」中「队尾」的操作与「单调递增栈」中「栈顶」的操作一致，即假设当前元素为 x，若队尾元素 <= x，则将 x 入队，否则不断弹出队尾元素，直至队尾元素 <= x。

例如以 3 1 4 5 2 7 为例，若「队首」始终不弹出元素，则其具体过程如下图所示。

由此可知，「单调队列」与「单调栈」的最大区别就在于「队首」的操作，「何时将队首元素出队」是「单调队列」算法的关键。

然而「队首」的操作往往具有多样性，并非一成不变，因此接下来我们以三道经典题型为例来进一步讲解该算法。

习题讲解

239. 滑动窗口最大值

题目描述

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

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

示例 1

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

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

示例 3

输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4

输入：nums = [9,11], k = 2
输出：[11]

示例 5

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

提示

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

题目讲解

「滑动窗口中的最大 / 小值」是「单调队列」最为经典的应用，其它「单调队列」的题型大多从该模型演变而来，因此大家需要着重理解此题。

由于本题求的是「滑动窗口中的最大值」，因此我们使用「单调递减队列来进行解决」。另外由于窗口大小为 k，所以当窗口右端点下标为 r 时，影响当前窗口最大值的元素下标范围为 [r-k+1, r]。

由此我们可以制定「队首」弹出元素的规则，即当「队尾元素的下标 – 队首元素的下标 + 1」大于 k 时，弹出「队首」元素。

接下来我们以 nums = [3 2 1 -1 2]、k = 3 为例，展示「单调递减队列」的具体执行过程。且为了便于展示，我们在「单调队列」中存储的是元素的下标，而不是元素的数值。

观察上述执行过程，我们可以发现元素入队分为两步，第一步是「不断弹出队尾元素」直至队尾元素代表的数值大于等于当前元素，第二步是「弹出队首元素」直至「当前元素下标 – 队首元素下标 + 1」小于等于 k。

进一步观察可以发现，当前元素入队的两步操作结束后，以当前元素为右端点的窗口，其窗口最大值为「队首元素」所对应的数值。

我们以当前元素为第四个元素（即 -1）为例来帮助大家理解。

此时队尾数值为 nums[3] = 1，即队尾数值大于等于当前元素，因此当前元素入队（队列中存储元素下标），如下图所示。

入队后「弹出队首元素」直至「当前元素下标 – 队首元素下标 + 1」小于等于 k，因此队首元素被弹出，最终状态如下图所示。

第四个元素完成上述两步入队操作后，队首元素下标为 2，其对应的数值 nums[2] = 2，当前窗口最大值 max([2 1 -1]) = 2。因此印证了刚才的结论，即当前元素入队的两步操作结束后，以当前元素为右端点的窗口，其窗口最大值为「队首元素」所对应的数值。

由此我们可以发现「单调队列」的核心功能为「求出数组中每一个元素其固定区间范围内的最大 / 小值」。并且由于每个元素出队、入队最多一次，因此总的时间复杂度为 O(n)。

根据上述算法即可解决本题，具体实现细节见下述代码。

代码实现

class Solution { 
   
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) { 
   
        int len = nums.size(), l = 0, r = -1;
        vector<int> q(len, 0), ans;
        for (int i = 0; i < len; i++) { 
   
            while (l <= r && nums[q[r]] < nums[i]) r--;
            q[++r] = i;
            if (i-q[l]+1 > k) l++;
            if (i >= k-1) ans.push_back(nums[q[l]]);
        }
        return ans;
    }
};

1425. 带限制的子序列和

题目描述

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

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

示例 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] 。

提示

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

题目讲解

本题求解的是最大「非空」子序列元素和，且相邻两个元素坐标差小于等于 k。由于题目的主体是子序列，因此我们采取一种「增量式」的思想来进一步思考。

假设当前有一个子序列 A，现在想在 A 后面再添加一个元素 x，则我们只需要考虑 x 和 A 中最后一个元素的坐标差是否小于等于 k，而不用考虑 A 中的所有元素。更明确地说，对于子序列 A，我们只需要记录它的元素和与最后一个元素的下标即可。

基于上述的思考，不难想到使用动态规划的算法，令 f[i] 表示以 nums[i] 为子序列最后一个元素时的最大元素和，则可以得到如下递推公式：
$$f[i]=\max (f[j],0)+nums[i](i-k\le j<i)$$

根据上述公式，我们可以得到一种暴力的做法，即对于每一个 i，向前枚举合法的 j 来更新 f[i]，时间复杂度为 O(nk)。

观察题目中的数据范围，暴力做法很明显无法通过，因此我们考虑如何优化。

f[i] 由前面 k 个数中的最大值转移而来，因此不难想到使用「单调队列」算法来进行优化。用「单调队列」来维护 f 数组中大小为 k 的窗口的最大值即可完成此题，时间复杂度优化至 O(n)，具体细节见代码。

通过此题，我们可以更深刻地意识到，「单调队列」在求取「数组中每一个元素其固定区间范围内的最大 / 小值」的作用。而也正是该功能，使得「单调队列」常作为「动态规划」的一种优化手段出现在面试题中。

代码实现

class Solution { 
   
public:
    int constrainedSubsetSum(vector<int>& nums, int k) { 
   
        int len = nums.size(), l = 0, r = -1, ans = nums[0];
        vector<int> q(len, 0);
        for (int i = 0; i < len; i++) { 
   
            if (l <= r && i - q[l] > k) l++;
            if (l <= r) nums[i] = max(nums[i], nums[i] + nums[q[l]]);
            ans = max(ans, nums[i]); 
            while (l <= r && nums[q[r]] < nums[i]) r--;
            q[++r] = i;
        }
        return ans;
    }
};

862. 和至少为 K 的最短子数组

题目描述

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1。

示例 1

输入：A = [1], K = 1
输出：1

示例 2

输入：A = [1,2], K = 4
输出：-1

示例 3

输入：A = [2,-1,2], K = 3
输出：3

提示

• 1 <= A.length <= 50000
• -1e5 <= A[i] <= 1e5
• 1 <= K <= 1e9

题目讲解

本题求解的是元素和大于等于 K 的最短非空连续子数组，由于涉及连续子数组和的求取，所以先对 A 做一个前缀和。

令 B 为 A 的前缀和数组，即 A 在 [x, y] 区间的元素和等于 B[y] – B[x-1]。又因为我们需要求解元素和大于等于 K 的最短连续子数组，即对于 B[y] 来说，找到最大的 x 满足 0 <= x < y 且 B[y] – B[x] >= K，也就是说，我们既希望 B[x] 小又希望 x 大。

基于上述观察，我们可以维护一个单调递增队列 [x1, x2, …, xp] 存储所有可能更新答案的下标 x（左边为队首）。队列满足从左至右，下标递增且下标对应的 B 中元素值也递增。

假设当前元素为 B[y]，若 B[xp] > B[y] 则弹出，因为 y 比 xp 更大且 B[y] 比 B[xp] 更小，即 y 一定比 xp 更优。基于该策略不断弹出队尾元素，直至条件不再满足。

对于队首元素来说，若 B[y] – B[x1] >= K，则弹出 x1 并更新答案 ans = min(ans, y – x1)。因为 y 是不断变大的，就算之后存在 y’ > y 满足 B[y’] – B[x1] >= K，y 距 x1 仍近于 y’，因此可以直接将 x1 弹出而不影响答案。基于该策略不断弹出队首元素，直至条件不再满足。

另外，上述算法未考虑到区间 [1, y] 的情况，因此若 B[y] >= K，则更新答案 ans = min(ans, y)。

观察上述算法，可以发现队尾操作与基础题「滑动窗口」没有区别，主要变化在于「队首弹出元素」的条件，而本题也正是通过对该条件的修改使得题目思维难度变大。

代码实现

class Solution { 
   
public:
    int shortestSubarray(vector<int>& A, int K) { 
   
        int len = A.size(), l = 0, r = -1, ans = len+1;
        vector<int> q(len, 0);
        for (int i = 1; i < len; i++) A[i] += A[i-1];
        for (int i = 0; i < len; i++) { 
   
            while (l <= r && A[q[r]] > A[i]) r--;
            q[++r] = i;
            while (A[q[r]]-A[q[l]] >= K) { 
   
                ans = min(ans, q[r]-q[l]);
                l++;
            }
            if (A[i] >= K) ans = min(ans, i+1);
        }
        if (ans == len+1) ans = -1;
        return ans;
    }
};

总结

通过上述三道例题的讲解，希望大家对于「单调队列」有了更多的了解，其实「单调队列」就是在「单调栈」的基础上加了一个「弹出队首」的操作，虽然该操作的添加极大地增加了该算法的多样性。

不过作为初学者，大家只需要理解「单调队列」在「滑动窗口」问题上的应用即可，即在 O(n) 时间复杂度内求出数组中每一个元素其固定区间范围的最大 / 小值。

至此我们完成了两大基础线性数据结构的讲解（单调栈与单调队列），这两个数据结构的变化较多，大家需要在日后刷题的过程中进一步地感受与体会，祝大家日益精进，刷题愉快！