博客转载

单调队列和单调栈（通俗易懂）

概念

单调队列和单调栈是一种基于队列和栈的高级数据结构，就是字面意思理解他们都保持自身内部的元素顺序单调，通过使用他们可以在 O(n) 的复杂度情况下解决查找一维数组最值的问题，虽然实现起来并不复杂但是使用起来非常的神奇高效，可以有效的解决许多问题

  • 单调栈由于只有一个口——后进先出的特性维护擅长最近的大于/小于的关系，从左向右入栈就是维护元素右侧的最近关系，从右向左入栈就是维护元素左侧的最近关系
  • 单调队列由于有两个口——先进先出的特性擅长维护指定区间的最大/最小值，最小值对应着递增队列，最大值对应着递减队列

单调栈

引入

考虑一个问题，对于一个数列我们希望知道每个元素后面比它小的第一个元素。常规的做法就是二重循环暴力查找，但是太慢了问题就在于如果为每个元素查找答案的时候都遍历会重复的查找根本根本不能作为答案的元素

比如上述我们在为 7 查找答案的时候我们找到了 6 返回答案这并没有问题，但是当我们为 6 找答案的时候需要遍历到 4 才能确定答案，此过程中我们遍历了不能作为答案的 8 和 9，在为 8 查找答案的时候也是需要遍历到 4 才能确定答案，此过程中我们不知悔改的又遍历了不能作为答案的 9，如果能实现一次性用 4 确定作为前面所有比它大的数的答案无疑会提高效率了

思想

栈先进后出的特点恰好能够帮助我们实现这种办法，每次遍历到某个元素的时候，先看看能不能作为前面已经入栈元素的答案，能的话就将前面元素的答案并弹出栈，然后自身入栈作为需要查找答案的元素等待后面入栈的元素确定为其答案。如果是查找最小值那么无疑栈内剩余的元素肯定是递增的，否则的话栈内剩余的元素就是递减的

分类

分为单调递增栈和单调递减栈，单调递增栈是元素从栈底到栈顶遵从从大到小的顺序，单调递减栈是元素从栈底到栈顶遵从小到大的顺序

模板

  • 遍历的顺序决定查找的答案是在元素的左边还是右边

  • 每次用遍历到的元素尝试能否作为之前元素（已经在栈内的元素）的答案，能的话将栈内元素弹出并记录答案，再讲该元素压入栈内等待后面的元素为其查找答案

1
2
3
4
5
6
7
8
9
//数组存储权值,stack对下标进行操作
stack<int> sk;
for (遍历这个数组) {
    while (栈不为空 && 当前元素可以作为栈顶元素的答案) {
        记录弹出栈顶元素答案;
        栈顶元素出栈;
    }
    当前元素入栈;
}

例题

每日温度

题意：请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数

思路：裸题,初始化每个元素的答案为 0，用单调栈更新每个位置的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
   public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> result(n, 0);  //默认都是没有比当天温度高的天
        stack<int> sta;
        for (int i = 0; i < n; ++i) {
            while (!sta.empty() && T[sta.top()] < T[i]) {  //用当前的元素去更新已经保存在栈内且比当前温度小的天数
                result[sta.top()] = i - sta.top();
                sta.pop();
            }
            sta.push(i);
        }
        return result;
    }
};

下一个更大元素 I

题意：给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1

思路：nums1 是 nums2 的子集，借助单调栈求出 nums2 的元素的答案然后将 nums1 内的元素需要的答案输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
   public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> mp;  //记录nums1中每个元素对应的答案
        stack<int> sta;
        const int n = nums2.size();
        for (auto e : nums2) {  //为nums2中的每个元素查找答案
            while (!sta.empty() && sta.top() < e) {
                mp[sta.top()] = e;
                sta.pop();
            }
            sta.push(e);
        }
        while (!sta.empty()) {
            mp[sta.top()] = -1;	//剩余的元素说明没有找到对应的答案
            sta.pop();
        }
        vector<int> result;
        for (auto e : nums1)	
            result.push_back(mp[e]);	//将nums1需要的答案返还
        return result;
    }
};

下一个更大元素 II

题意：给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1

思路：元素的前后方向的元素都可以是其答案，遍历两次数组就可以保证前后的元素都用来更新当前元素了，开始想着是复制一次数组接在后面，实际上实现起来还不如直接取模模拟循环呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
   public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);  //还是先都假设为-1然后用后面的数去更新当前的数
        stack<int> sta;
        for (int i = 0; i < n * 2; ++i) {
            while (!sta.empty() && nums[sta.top()] < nums[i % n]) {
                result[sta.top()] = nums[i % n];
                sta.pop();
            }
            sta.push(i % n);
        }
        return result;
    }
};

写代码的时候开始想着是先给每个元素找答案，然后栈内最终剩余的元素答案记为 -1，这是不对的因为可能起初当前元素的后面的元素作为当前元素的答案了，但是第二遍前面的元素未能作为当前元素，记为 -1 导致覆盖了答案

最大矩形面积

题意

思路：对于当前位置，以它的高度作为矩形的最大面积就是左边和右边第一个比它矮的矩形之间距离乘上它自身的高度，所以我们用两个单调栈分别维护出每个位置左边和右边第一个比它矮的矩形的位置，然后求出用每个位置高度作为矩形的最大面积并尝试更新答案

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
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;

int h[maxn], l[maxn], r[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> h[i];
        stack<int> sk;
        //为每个矩形找出右侧第一个比它小的矩形的位置
        for (int i = 1; i <= n; ++i) {
            while (!sk.empty() && h[i] < h[sk.top()]) {
                r[sk.top()] = i;
                sk.pop();
            }
            sk.push(i);
        }
        while (!sk.empty()) {
            r[sk.top()] = n + 1;
            sk.pop();
        }
        //为每个矩形找出左侧第一个比它小的矩形的位置
        for (int i = n; i >= 1; --i) {
            while (!sk.empty() && h[i] < h[sk.top()]) {
                l[sk.top()] = i;
                sk.pop();
            }
            sk.push(i);
        }
        while (!sk.empty()) {
            l[sk.top()] = 0;
            sk.pop();
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, (r[i] - l[i] - 1) * h[i]);
        cout << ans << endl;
    }
    return 0;
}

单调队列

引入

之前单调栈解决的问题是查找元素之前或者之后的最值元素，现在我们要求数列某个区间内的最值问题（经典的滑动窗口问题）

例如下面的问题，求出该序列连续 3 个元素中的最小值和最大值，暴力二重循环查找还是可以解决的但是可以进一步优化，一个方法是对于区间的数用优先队列存储这样队首答案就是每次滑动窗口的答案，复杂度为 O(nlogn)，另一种方法就是复杂度更低的单调队列

为什么暴力查找效率低还是因为重复操作的问题，比如对于上述问题查找区间最大值时，第三行 [-1 -3 5] 中因为 5 比前两个数更大而且位置更靠后，那么前面的数肯定不会作为后续的答案（最优解）了，因为后续区间若是选前面的数作为答案能么这个数就可以更新他们了。我们称某个元素能否做位备选答案的能力为潜力值，那么后续的数如果比前面的数潜力值大的话无疑前面的数就肯定不会成为备选的答案了就可以直接舍弃了

思想

为了实现上述需求，我们需要一个数据结构能够像单调栈那样按照单调的顺序存储能作为备选的答案元素如此每次从边上去出来的就可以作为答案了，同时还要使取出来的元素作为答案的同时满足处于区间范围内，无疑第一个需求一个口的单调栈从尾部维护内部的元素就可以实现，那么第二个要求还需要从头部维护内部的元素淘汰掉虽然可以作为备选答案但是已经不再区间范围内的元素，结合两者考虑借助双端队列就可以满足上述的需求，遍历到当前元素的时候先将队内肯定不能作为备选答案的元素逐一淘汰，然后将该元素插入队尾，同时判断队首元素是否在区间范围内，不在的话同样淘汰掉，最终队内的元素保持单调且都在区间范围内从队首取出的元素就是答案了

分类

分为单调递增队列和单调递减队列，单调递增队列内的元素从队首到队尾遵从从小到大的顺序，每次从队首取出的元素都是区间内的最小值，单调递减队列内的元素从队首到队尾遵从从大到小的顺序，每次从队首取出的元素都是区间内的最大值

模板

1
2
3
4
5
6
7
8
//数组记录权值,que对下标进行操作
int que[maxn], hh = 0, tt = -1;  //模拟双端队列或者借助deque
for (遍历这个数组) {
    while (队列不为空 && 当前元素的潜力值大于队尾元素的潜力值) 淘汰没用的队尾元素;
    当前元素入队;
    if (队列不为空 && 队首的元素不在区间范围内) 淘汰没用的队首元素
    取出队首的元素作为该区间的答案;
}

淘汰队首元素用 if 是因为每次滑动窗口只是向后一个位置，所以脱离范围的元素顶多也就一个，如果滑动的距离更远了那么这里应该用 while 了

例题

滑动窗口最大值

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

思想：裸题唯一需要注意的是的没形成第一个区间的时候是不记录答案的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
   public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        int que[n];
        int hh = 0, tt = -1;
        for (int i = 0; i < n; ++i) {
            while (hh <= tt && nums[que[tt]] <= nums[i]) --tt;  //淘汰没用元素
            que[++tt] = i;                                      //尾插法
            if (hh <= tt && que[hh] <= i - k) ++hh;             //删除没用的头元素
            if (i < k - 1) continue;                            //前k-1个元素还没组成一个区间不取答案
            res.push_back(nums[que[hh]]);                       //确定一个区间的答案
        }
        return res;
    }
};

切蛋糕

题意：小Z过生日，现在有 N 个蛋糕，每个蛋糕对应一个幸运值（有正有负），小Z最多连续吃 M 块蛋糕（可以少吃），让你找到一个吃法让获取的幸运值总和最大

思路：朴素算法 TLE。连续求和借助前缀和，两个边界相减找出最大值即可，那么对于区间长度 M 内我们找出前缀和最小的位置作为左边界，当前元素（区间末尾元素）作为右边界两者相减就是当前区间内的最优解，用所有区间的最优解维护答案即可。那么我们先求出每个位置对应的前缀和然后借助单调队列求最小值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;

int suff[maxn], que[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> suff[i], suff[i] += suff[i - 1];  //处理前缀和
    int hh = 0, tt = -1;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, suff[i] - suff[que[hh]]);            //每次去除最小值更新一次答案
        while (hh <= tt && suff[que[tt]] >= suff[i]) --tt;  //队尾淘汰不能作为答案的元素
        que[++tt] = i;
        if (hh <= tt && que[hh] <= i - m) ++hh;  //队首淘汰不在区间范围内的元素
    }
    cout << ans << endl;
    return 0;
}

为什么不像上述前 m-1 个元素先不更新答案呢，因为题目是最多是 m 个可以少吃所以从一开始每次遍历一个元素就要尝试更新答案，过程中连续 m 个元素找最大值也就包含了吃不够 m 个的情况

总结

  • 单调栈和单调队列都是因为保证了每个元素最多被查看一次，去除了被多次遍历的情况所以复杂度成功降到了 O(n)
  • 两者对照看原理很像，因为查找最近的最值没有范围限制自然一个口维护就可以了，查找区间的最值涉及窗口的滑动存在范围所有在上述的基础上还要再多一个口维护，他们自身内部都是单调的存储元素实现记录答案
  • 这篇博客还是没能把核心的思想表述出来，还是多看多体会吧 😅，虽然不难但是应用广泛且以后找工作面试好像常考