算法沉淀——栈（leetcode真题剖析）

栈（Stack）是一种基于先进后出（Last In, First Out，LIFO）原则的数据结构。栈具有两个主要的操作：

1. 压栈（Push）：将元素添加到栈的顶部。
2. 出栈（Pop）：从栈的顶部移除元素。

栈常常用于需要反转操作顺序的场景，或者在需要记录操作历史的情况下。在算法中，栈的应用广泛，以下是一些典型的栈算法：

1. 括号匹配问题：使用栈来检查表达式中的括号是否匹配，例如检查 ()、[]、{} 是否正确嵌套。
2. 逆波兰表达式求值：通过栈来实现对逆波兰表达式的求值，其中操作数和操作符都存储在栈中。
3. 函数调用栈：在编程语言中，函数调用时的执行过程通常使用函数调用栈（Call Stack）来管理。
4. 深度优先搜索（DFS）：在图或树的遍历过程中，使用栈来实现深度优先搜索。
5. 迭代法求解二叉树的前序、中序、后序遍历：通过栈来模拟递归过程，实现二叉树的不同遍历方式。
6. 表达式求值：将中缀表达式转换为后缀表达式，然后使用栈求解后缀表达式的值。
7. 迷宫求解：通过栈来记录路径，实现对迷宫的求解过程。

栈的特性使其在某些问题场景中非常有效和方便。在算法设计和实现中，栈通常用于临时存储数据、回溯操作、深度优先搜索等。

01.删除字符串中的所有相邻重复项

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

思路

这里使用栈的思想可以很好的解决这个问题，我们每插入一个字符前进行对比，如果栈顶存在该字符，则删除栈顶字符且不插入，否则插入字符，最后留在栈中的字符就是需要返回的，考虑到字符顺序的问题，我们可以直接用字符串来直接模拟栈。

代码

class Solution {
public:string removeDuplicates(string s) {string ret;for(int i=0;i<s.size();++i){if(ret.size()&&s[i]==ret.back()) ret.pop_back();else ret+=s[i];}return ret;}
};

02.比较含退格的字符串

题目链接：https://leetcode.cn/problems/backspace-string-compare/

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

思路

同样我们使用栈的思想，分别使用两个空字符串来模拟栈，遇到#字符就出栈，其他时候进栈，最后比较两个字符串即可。

代码

class Solution {
public:bool backspaceCompare(string s, string t) {string s1,s2;for(int i=0;i<s.size();++i){if(s[i]=='#') {    if(s1.size()) s1.pop_back();}else s1+=s[i];}for(int i=0;i<t.size();++i){      if(t[i]=='#') {    if(s2.size()) s2.pop_back();}else s2+=t[i];}return s1==s2;}
};

03.基本计算器 II

题目链接：https://leetcode.cn/problems/basic-calculator-ii

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

• 1 <= s.length <= 3 * 105
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

思路

根据题目要求我们只需要考虑空格、数字和四个运算符这几种情况，我们可以使用一个数组来模拟栈插入每一个数，使用一个前缀字符来进行运算符的标记，初始设为加，当我们碰到加减都更新，碰到乘除就直接在栈顶计算，直至字符串结束，最后我们将栈中的数相加即可。

代码

class Solution {
public:int calculate(string s) {vector<int> st;char op='+';int n=s.size(),i=0,ret=0;while(i<n){if(s[i]==' ') i++;else if(s[i]>='0'&&s[i]<='9'){int tmp=0;while(i<n&&s[i]>='0'&&s[i]<='9') tmp=tmp*10+(s[i++]-'0');if(op=='+') st.push_back(tmp);else if(op=='-') st.push_back(-tmp);else if(op=='*') st.back() *=tmp;else if(op=='/') st.back() /=tmp;}else op=s[i++];}for(int& i:st) ret+=i;return ret;}
};

04.字符串解码

题目链接：https://leetcode.cn/problems/decode-string/

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

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

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

思路

这里我们要使用栈来解决问题，我们需要模拟每一种情况的发生，以及细节的处理，我们建立一个重复数的栈和一个字符串的栈，遇到数字，放入数字栈中，遇到左括号，把后面的字符串提取出来，放入字符串栈中，遇到了右括号，解析然后放到字符串栈顶字符串之后，遇到单独字符放到字符串栈顶字符串之后，最后栈顶的字符串即为我们需要的字符串。

代码

class Solution {
public:string decodeString(string s) {// 使用两个栈，一个用于存储字符串，另一个用于存储数字stack<string> st;stack<int> nums;// 初始化栈，将一个空字符串入栈，用于存储当前解码的结果st.push("");int i = 0, n = s.size();// 遍历输入字符串while (i < n) {// 如果当前字符是数字，解析数字并入数字栈if (s[i] >= '0' && s[i] <= '9') {int tmp = 0;while (s[i] >= '0' && s[i] <= '9') tmp = tmp * 10 + (s[i++] - '0');nums.push(tmp);}// 如果当前字符是'['，入栈一个空字符串，用于存储当前括号内的解码结果else if (s[i] == '[') {i++;string tmp;while (s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];st.push(tmp);}// 如果当前字符是']'，将栈顶字符串重复相应次数后，与前一个栈顶字符串拼接else if (s[i] == ']') {string tmp = st.top();st.pop();int k = nums.top();nums.pop();while (k--) st.top() += tmp;i++;}// 如果当前字符是字母，将字母拼接到栈顶字符串else {string tmp;while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];st.top() += tmp;}}// 最终栈中存储的即为解码结果return st.top();}
};

05.验证栈序列

题目链接：https://leetcode.cn/problems/validate-stack-sequences/

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

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

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed 的所有元素 互不相同
• popped.length == pushed.length
• popped 是 pushed 的一个排列

思路

这里我们可以直接用一个栈来模拟这个过程，当栈为空则说明相匹配，否则就说明不匹配

代码

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i=0,n=popped.size();for(int& x:pushed){st.push(x);while(!st.empty()&&st.top()==popped[i]){st.pop();i++;}}return st.empty();}
};