单调栈/单调队列

发表于 更新于 分类于 Artalk： loading...

单调栈/单调队列是一类特殊的数据结构，保证容器内元素的值是单调变化的。「栈」或者「队列」影响的是元素进入或者出容器的顺序

这里的栈，也可以看作一个只能右端输入和输出的双端队列Deque

无论是栈还是队列，在具体实现时，都是要及时移除影响性质的元素（一般都是无用元素），保持容器内元素的单调性。

具体来说，单调栈常用于求，诸如「上一个最大元素」、「下一个最小元素」等问题，根据栈内元素是单调递减还是单调递增具体判断。

单调栈

496.下一个更大元素I

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1

示例：

1
2
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]

分析：

可以直接对 nums2 进行遍历，求出每个元素的下一个更大的元素，由于是「下一个」，所以从右向左遍历

目的是求临近的最大元素，因此需要维持一个单调递减栈，当栈顶元素小于或等于当前元素时，弹出；直至栈顶元素大于当前元素

此时栈顶元素就是距离当前元素最近的「更大元素」，再将当前元素入栈的话，也保证了栈内元素的单调性

借助哈希表保存结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> mp = new HashMap<>();
        Deque<Integer> st = new LinkedList<>();
        int n2 = nums2.length;
        for (int i = n2 - 1; i >= 0; --i) {
            while (!st.isEmpty() && st.peekLast() <= nums2[i]) st.pollLast();
            mp.put(nums2[i], st.isEmpty() ? -1 : st.peekLast());
            st.offerLast(nums2[i]);
        }
        for (int i = 0; i < nums1.length; ++i) {
            nums1[i] = mp.get(nums1[i]);
        }
        return nums1;
    }
}

503. 下一个更大元素 II

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        int n = nums.size();
        vector<int> res(n);
        for (int i = 2 * n - 1; i >= 0; -- i) {
            int num = nums[i % n];
            while (!st.empty() && num >= st.top()) {
                st.pop();
            }
            // 注意有重复的元素 哈希表也好 数组也好 要存序号；
            res[i % n] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        return res;
    }
};

剑指 Offer 30. 包含min函数的栈

问题描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(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
class MinStack {

    /** initialize your data structure here. */
    private Deque<Integer> st, stt;
    public MinStack() {
        this.st = new LinkedList<>();
        this.stt = new LinkedList<>(); // 维持一个单调递减的栈
    }
    
    public void push(int x) {
        st.offerLast(x);
        if (stt.isEmpty() || stt.peekLast() >= x) stt.offerLast(x);
    }
    
    public void pop() {
        int val = st.pollLast();
        if (val == stt.peekLast()) stt.pollLast();
    }
    
    public int top() {
        return st.peekLast();
    }
    
    public int min() {
        return stt.isEmpty() ? -1 : stt.peekLast();
    }
}

单调栈的其他题目（题单来自0x3f）：

矩形系列

贡献法？

单调队列

剑指 Offer 59 - II. 队列的最大值

问题描述：

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

若队列为空，pop_front 和 max_value 需要返回 -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
class MaxQueue {
    private Deque<Integer> q, qq;
    public MaxQueue() {
        this.q = new LinkedList<>();
        this.qq = new LinkedList<>();
    }
    
    public int max_value() {
        return q.isEmpty() ? -1 : q.peekFirst();
    }
    
    public void push_back(int value) {
        while (!q.isEmpty() && q.peekLast() <= value) q.pollLast();
        q.offerLast(value);
        qq.offerLast(value);
    }
    
    public int pop_front() {
        if (qq.isEmpty()) return -1;
        int cur = qq.pollFirst();
        if (cur == q.peekFirst()) q.pollFirst();
        return cur;
    }
}


239. 滑动窗口最大值

问题描述

image-20221026194650025

思路

如果用普通队列来做

用一个队列来维持窗口内的所有值，遍历整个队列，求最小值；每次窗口向后移动，将新元素插入队尾，将队头删除。

时间复杂度O(nk)O(nk)

使用单调队列

维持一个单调递减队列，限制左端出队，右端入队和出队。

有点像「求上一个最大元素」，这种数据结构可以保证：

  1. 任何一个元素的左侧元素都是比当前元素大的（单调性质）；

  2. 并且左侧元素「在原数组的序号」一定比当前元素小（意味着要先出窗口的范围）

具体实现上，从左向右遍历，如果队列最右端的元素小于或等于当前元素，则出队

解释：此时最右端元素一定不会是当前窗口的最大值，为无用元素，要移除以保证队列的单调性）

​ 如果队列左端元素超出窗口范围，就出队，这样控制下，单调递减队列的最左端一定是当前窗口的最大值

代码

使用数组模拟

acwing 154. 滑动窗口

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
45
46
47
48
#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N]; // 队列中存储的是序号

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int hh = 0, tt = -1;
    // 求窗口内的最小值
    for (int i = 0; i < n; i ++ )
    {
        // 判断当前队头是否还在窗口内
        // Ex：k=3 【0 1 2 3】 4 5 6 7 
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
        // 队尾部元素大于当前元素，判定为冗余的，移除
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        // 将当前元素入队
        q[ ++ tt] = i;
        // 最终维持一个单调递增的队列

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    hh = 0, tt = -1;
    // 求窗口内的最大值
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (!q.isEmpty() && i - k == q.peekFirst()) q.pollFirst(); // 如果要移除当前窗口的正好是最大元素
            while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) q.pollLast(); // 单调递减队列
            q.offerLast(i);
            if (i >= k - 1) res[i - k + 1] = nums[q.peekFirst()];
        }
        return res;
    }
}

其他例题

1438. 绝对差不超过限制的最长连续子数组

问题描述

image-20221026194855320

简单分析

使用双指针维持一个滑动窗口，然后用两个单调队列维持窗口内的最大值和最小值（因为最大绝对差=最大值-最小值）

双指针算法参照本站博文，其他参见代码注释

代码实现

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
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        // 最大的绝对差，肯定是最大值减去最小值
        // 两个单调队列
        int n = nums.length;
        Deque<Integer> incrQ = new LinkedList<>(), decrQ = new LinkedList<>();
        int l = 0, r = 0, res = 0;
        while (r < n) {
            // 单调递减队列维持当前窗口的最大值
            while (!decrQ.isEmpty() && nums[decrQ.peekLast()] < nums[r]) decrQ.pollLast();
            decrQ.offerLast(r);
            // 单调递增队列维持当前窗口的最小值
            while (!incrQ.isEmpty() && nums[incrQ.peekLast()] > nums[r]) incrQ.pollLast();
            incrQ.offerLast(r);
            
            // 为了使窗口满足要求，left 指针被动右移
            while (!decrQ.isEmpty() && !incrQ.isEmpty() && nums[decrQ.peekFirst()] - nums[incrQ.peekFirst()] > limit) {
                if (decrQ.peekFirst() == l) decrQ.pollFirst();
                if (incrQ.peekFirst() == l) incrQ.pollFirst();
                l++;
            }
            // 阶段结果
            res = Math.max(res, r - l + 1);
            // right 指针主动右移，破坏当前窗口
            r++;
        }
        return res;
    }
}

接下来一个进阶题目

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

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

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

注意：数组内可能会有负数

如果保证数组内全部为正整数，题目就变成了209. 长度最小的子数组，可以选择双指针做法或者二分查找

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        // 最朴素想法，用前缀和数组
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + nums[i];
      
        int res = n + 1;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i <= n; ++i) {
            long cur = prefix[i];
            while (!q.isEmpty() && cur - prefix[q.peekFirst()] >= k) {
                res = Math.min(res, i - q.pollFirst());
            }
            while (!q.isEmpty() && prefix[q.peekLast()] >= cur) q.pollLast();
            q.offerLast(i);
        }
        return res > n ? -1 : res;
    }
}