堆栈

本文将针对堆栈相关知识进行讲解。

栈

栈是一种先入后出的数据结构

栈的操作

栈的基本操作

栈有两个基本操作，push和pop。

栈的特殊操作

判断某个序列是否为栈的有效弹出序列

LeetCode 面试题31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

思路

采用贪心算法，创建一个栈，将pushed中的元素依次压入，然后判断栈顶的元素是否等于pop中指定的元素，如果是就出栈，最后判断栈是否为空即可。

代码

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> num_stack{};
    int i=0;
    for(auto &v : pushed){
        num_stack.push(v);
        while(i<popped.size() && !num_stack.empty() && popped[i] == num_stack.top()){
            num_stack.pop();
            i++;
        }
    }
    return num_stack.empty();
}

特殊的栈

单调栈

单调栈，顾名思义其中的元素是单调递增或单调递减的，单调栈在有些情况下很有用，例如获得一个数组中的递增子序列等。

单调栈应用场景

503. 下一个更大元素 II

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

思路

给定一个普通的数组，如果我们想要按照循环的方式对其进行处理，那么可以采用求余的方法，当超过了数组长度，就对数组长度求余，这样就可以开始循环。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return vector<int>{};
        vector<int> ans(n, -1);

        stack<int> s{};
        for (int i = 0; i < 2 * n; ++i) { 
            int cur_num = i % n;
            while (!s.empty() && nums[s.top() % n] < nums[cur_num]) { 
                ans[s.top() % n] = nums[cur_num];
                s.pop();
            }
            s.push(i); 
        }
        return ans;
    }
};

402. 移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

思路

利用栈的贪心算法，对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，例如，对于 $A = 1axxx，B = 1bxxx$，如果 $a > b$ 则 $A > B$。所以在删除数字时应当从左向右迭代。
在确定了迭代顺序后，我们需要制定如何删除数字的标准，为了讨论方便，我们利用下面的例子进行说明：对于序列$425$，如果要求我们只删除一个数字，那么从左到右，我们有 4、2 和 5 三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始，小于它的左邻居 4。则我们应该去掉数字 4。如果不这么做，则随后无论做什么，都不会得到最小数。

任务

• 确定迭代顺序
• 制定删除数字标准

84. 柱状图中最大的矩形

思路

1.暴力法

暴力法依次遍历每一个高度，分别向两边延伸，寻找严格小于当前位置高度的矩形，然后计算长度，求得面积。最坏情况下，每次延伸的复杂度为$O(n)$，所以总复杂度为$O(n^2)$

2.空间换时间的单调栈法

我们可以利用一个栈，栈中元素保存的是数组下标$j_1,j_2,…,j_s$，同时保证$height[j_1]height[s.top]$，此时说明我们找到了以$i$为下标的高度的左侧边界，这就是对暴力法的优化。因此，我们需要两个数组，分别保存$i$的左边界和右边界。

最小栈

最小栈应用场景

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

思路

使用辅助栈的方式，将数据和最小值分别保存至两个栈中。当添加新数据时，如果新数据比辅助栈的栈顶数据还要小，那么就添加至栈中，否则没有必要更新辅助栈；当删除数据时，如果两个栈栈顶元素相同，则同时删除，否则只删除数据栈元素。

895. 最大频率栈

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。FreqStack 有两个函数：

• push(int x)，将整数 x 推入栈中。
• pop()，它移除并返回栈中出现最频繁的元素。如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

示例：

输入：
[“FreqStack”,”push”,”push”,”push”,”push”,”push”,”push”,”pop”,”pop”,”pop”,”pop”],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

思路

这道题一开始想用双向链表做，但是仔细考虑了一下，双向链表虽然能够有效地进行添加或删除操作，但是由于最频繁的元素不只一个，无法用某种有效手段判断当前应该删除哪一个元素。因此我们还是从栈的角度考虑问题。我们需要解决如下几个问题：

• 如何统计元素频率：使用哈希表
• 在具有相同的（最大）频率的元素中，怎么判断那个元素是最新的：我们可以使用栈来查询这一信息：靠近栈顶的元素总是相对更新一些。

因此我们需要创建两个map，一个用于保存元素频率，另一个保存频率到该频率下的所有元素映射，例如输入的例子为：1 2 3 1 1 3 3 4 5，则产生的栈如下：

5
4
3
2           3           3
1           1           1
频率为1      频率为2      频率为3

每次添加元素，我们将元素添加至对应的频率的栈中，删除时删除对应最大频率的栈顶元素即可

栈的一些应用场景

栈的一个典型应用是配对问题，如括号的配对。

括号匹配问题

LeetCode 1021 删除最外层括号

输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

本题目分为两步，第一步是对字符串进行原语化分解，这里就用到了栈，当栈为空时，意味着找到了一个原语

394. 字符串解码²

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

> 输入：s = "3[a]2[bc]"
> 输出："aaabcbc"
>

思路

这个题目本质上是一个括号配对问题，因为我们需要从内向外生成拼接字符串，和栈先入后出特性一致。当我们遇到左括号时，将数字和当前得到的字符串入栈，而当我们遇到右括号时，令res = last_res + cur_counter * res，其中last_res为上一个字符串，即栈顶的字符串。

代码

class Solution {
public:
    string decodeString(string s) {
        string res{};
        stack<int> counter_stack{};
        stack<string> res_stack{};
        int counter = 0;
        for(auto&v : s){
            if(v >= '0' && v <= '9') counter = counter*10 + (v-'0');
            else if(v == '['){
                /*
                **    保存该括号的重复次数
                */
                counter_stack.push(counter);

                /*
                **    将括号外的结果进行保存
                */
                res_stack.push(res);
                /*
                **    重置计数器和答案（因为答案已经保存在栈中）
                */
                counter = 0;
                res = {};
            }
            else if(v == ']'){
                int repeat_time = counter_stack.top();
                counter_stack.pop();
                string temp{};
                /*
                **    res 保存括号内的字符，而栈顶保存当前括号重复次数
                */ 
                for(int i=0;i<repeat_time;i++){
                    temp += res;
                }
                /*
                **    将括号外的字符串和括号中重复的字符串进行拼接
                */
                res = res_stack.top() + temp;
                res_stack.pop();
            }
            else{
                res.push_back(v);
            }
        }
        return res;
    }
};

LeetCode 232 用栈实现队列

一看这道题，栈和队列一个FIFO一个FILO，怎么能用栈实现队列呢？这里使用了两个栈，一个进行入队操作，一个进行出队操作。

LeetCode 768 最多能完成排序的块

arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

解题思路¹：

• 排序块定义：

  • 设一个块中最大数字为$h$, 若块后面的所有数字都$>=h$ ，则此块为排序块。排序块最短长度为1。

  例如，对于数组[1 2 1 3 4 7 5 6]，可以划分为：[1 | 2 1 | 3 | 4 | 7 5 6] 共5个排序块

• 贪心法则：

专题：语法分析

栈由于其先入后出的特性，可以用来进行语法特性分析，本专题将针对栈进行语法特性分析的一些场景进行总结。首先，在进行语法分析时，我们要明确何时进行入栈操作，何时进行出栈操作。以下题为例

71. 简化路径

首先，在分析路径时，我们需要根据'/'对路径进行分割，然后看得到的所有操作符号，如果是".."进行出栈操作，如果是"."或""则跳过，如果是普通路径，进行入栈操作。

堆

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆(优先队列)、斐波那契堆等。如果有问题要求从小到大或从大到小，可以考虑维护一个最小堆。或者按照如下方式构造堆：

优先队列（大小顶堆）

在C++中，优先队列即为大顶堆的实现，可以利用优先队列，实现堆排序的功能，当然，由于队列是先进先出的，因此每次只能得到最大值，如果想获得任意值，可以维护一个set作为优先队列，set是排序的，且可以获得其中任意值。或者按照如下方式构造堆：

priority_queue<int, vector<int>, greater<int>> //小顶堆

如果想要获得前K小的元素，可以考虑维护一个大顶堆，然后依次将元素插入堆中，并保证堆的大小始终为K，如果超过K，将堆顶元素弹出。同理，如果获得前K大的元素，可以用小顶堆。(大用小，小用大)。

参考文献

---

1. 1.LeetCode 768 题解 ↩
2. 2.LeetCode394题解 ↩