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

在这里插入图片描述

算法沉淀——栈

01.删除字符串中的所有相邻重复项
02.比较含退格的字符串
03.基本计算器 II
04.字符串解码
05.验证栈序列

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

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

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

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

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

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

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

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

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

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

示例：

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

提示：

1 <= S.length <= 20000
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();
    }
};