算法数据结构

极值栈与极值队列

字数统计: 2.2k字   |   阅读时长: 9分
, ,

摘要: 极值栈，极值队列

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

极值栈是指除了维护栈的基本功能之外，还需要随时查询栈中的最值。它的设计思想是用两个栈来维护，其中一个栈维护数据的插入删除，另一个栈维护最值。

极值栈问题大家讨论的非常多，不过全是针对这个数据结构本身，暂时还没看到极值栈有什么实际的应用。

不过设计思想类似的极值队列还是有所应用的，本文我们首先介绍极值栈的设计思想，然后用类似的设计思想给出极值队列的代码模板，然后用极值队列解决设计自助结算系统问题以及滑动窗口最大值问题。

极值栈 (最小值)

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

提示：

1
2
3
-2^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3e4 次

示例 1:
输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); —> 返回 -3.
minStack.pop();
minStack.top(); —> 返回 0.
minStack.getMin(); —> 返回 -2.

算法：双栈

首先用一个常规的栈 st 来维护栈的基本操作，包括 push(x)、pop()、top()。

然后用另一个栈 st_min 来维护栈内的最小值。这个 st_min 需要满足以下条件：

  • st_min 从栈底到栈顶是从大到小的，栈顶最小，代表此时栈内的最小值。
  • 当 st 压入时，记压入元素为 x：
    • 如果 x > st_min.top()，那 x 的压入不会对栈内的最小值产生影响，原因在于 st_min 中元素都比 x 更早入栈，那 x 自然也会比 st_min.top() 中元素早出栈，因此 x 存在于 st 中的整个过程中，st_min.top() 始终都在，那就轮不到 x 成为 st 的最小值。
    • 若 x <= st_min.top()，那就将 x 压入 st_min，st_min 依然保持从底到顶递减的特性，从此时开始 x 就成为了 st 的最小值。但 st_min 中原有的元素不能弹出。因为 x 比它们更晚入栈意味着更早出栈，x 出栈后，st_min 原有的元素就要恢复其最小值的身份了。
  • 当 st 弹出时，记弹出的元素为 x = st.pop()。
    • 如果 x == st_min.top()，意味着 x 是 st 的最小值，则将 x 从 st_min 中弹出，最小值 x 在 st 中可能有多个，这些重复的最小值在 st_min 中都有记录。
    • 如果 x > st_min.top()，则当前元素的弹出对栈内最小元素无影响。

代码 (模板，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
33
34
35
36
37
38
class MinStack {
public:
    MinStack() {
        st = stack<int>();
        st_min = stack<int>();
    }

    void push(int x) {
        st.push(x);
        if(st_min.empty() || x <= st_min.top())
            st_min.push(x);
    }

    void pop() {
        if(st.empty())
            return;
        int top_item = st.top();
        st.pop();
        if(top_item == st_min.top())
            st_min.pop();
    }

    int top() {
        if(st.empty())
            return -1;
        return st.top();
    }

    int getMin() {
        if(st.empty())
            return -1;
        return st_min.top();
    }

private:
    stack<int> st;
    stack<int> st_min;
};

极值队列 (最大值)

问题与极值栈类似。

设计一个支持 push_back，pop_front，back()，front() 操作，并能在常数时间内检索到最大元素的队列。

实现 MaxQueue 类:

  • MaxQueue() 初始化队列。
  • void push_back(int val) 将元素val推入队列尾部。
  • void pop_front() 删除队列头部的元素。
  • int back() 获取队列尾部的元素。
  • int front() 获取队列头部的元素。
  • int getMax() 获取队列中的最大元素。

算法：双队列

与最小栈问题类似，唯一不同的一点就是：最小栈问题中新压入去的值 x 也是先弹出，这样栈中已有的先压入的元素的最小值不会受到新压入的 x 影响。

在极值队列中，因为队列先进先出的特性，队列当前的最大值不光受新压入的值 x 的影响，同时也受弹出元素的影响。因此队列中已有的先压入的元素的元素的最值就会收到新压入的 x 影响。

用一个队列 q 维护队列的基本操作，包括 push_back(x)、pop_front()、back()、front()。

另一个队列 deq_max 维护队列的最大元素，由于维护的过程中在头部和尾部都要弹出，因此要用双端队列。

当 q 弹出一个元素 x 时，如果 x 是 deq_max 的队头元素，则将 x 从 deq_max 弹出，x 后续不再对队列中的最值有影响。

当 q 压入一个元素 x 时，如果 deq_max 尾部有比 x 更小的元素，由于先进先出特性，这些更小元素在弹出之前，x 在 q 中始终都在，因此轮不到这些更小元素作为队列的最大值，因此将这些元素从 deq_max 尾部弹出。这样 deq_max 维持一个从队头到队尾单调递减的特性。

代码 (模板，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
33
34
35
36
37
38
39
40
41
42
43
44
45
class MaxQueue {
public:
    MaxQueue() {
        q = queue<int>();
        deq_max = deque<int>();
    }

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

    void pop_front() {
        if(q.empty())
            return;
        int top_item = q.front();
        q.pop();
        if(top_item == deq_max.front())
            deq_max.pop_front();
    }

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

    int back() {
        if(q.empty())
            return -1;
        return q.back();
    }

    int getMax() {
        if(q.empty())
            return -1;
        return deq_max.front();
    }

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

设计自助结算系统

LCR 184. 设计自助结算系统

请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：

  • get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1
  • add(value)：将价格为 value 的商品加入待结算商品队列的尾部
  • remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1

注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)

提示：

1
2
1 <= get_max, add, remove 的总操作数 <= 10000
1 <= value <= 1e5

示例 1：
输入:
[“Checkout”,”add”,”add”,”get_max”,”remove”,”get_max”]
[[],[4],[7],[],[],[]]
输出: [null,null,null,7,4,7]

示例 2：
输入:
[“Checkout”,”remove”,”get_max”]
[[],[],[]]
输出: [null,-1,-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
class Checkout {
public:
    Checkout() {
        max_q = MaxQueue();
    }
    
    int get_max() {
        return max_q.getMax();
    }
    
    void add(int value) {
        max_q.push_back(value);
    }
    
    int remove() {
        int ans = max_q.front();
        max_q.pop_front();
        return ans;
    }

private:
    MaxQueue max_q;
};

滑动窗口最大值

239. 滑动窗口最大值

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

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

提示：

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

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

算法：极值队列

滑动窗口最大值的标准解法为单调队列，参考文章 单调队列。

而如果直接使用维护最大值的极值队列，逻辑会非常清晰，不过这依赖于我们已经实现了 MaxQueue。事实上 MaxQueue 中的 deq_max 其实就是单调队列，相当于把单调队列的逻辑封装进了 MaxQueue。

代码 (C++)

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) {
        MaxQueue max_q;
        int n = nums.size();
        vector<int> result(n - k + 1);
        for(int i = 0; i < k; ++i)
            max_q.push_back(nums[i]);
        result[0] = max_q.getMax();
        for(int i = k; i < n; ++i)
        {
            max_q.pop_front();
            max_q.push_back(nums[i]);
            result[i - k + 1] = max_q.getMax();
        }
        return result;
    }
};
Share