栈（典型算法思想）—— OJ例题算法解析思路

一、1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

算法代码：

1. 初始化结果字符串

2. 遍历输入字符串

3. 检查和处理字符

4. 返回结果

总结

二、844. 比较含退格的字符串 - 力扣（LeetCode）

算法代码：

1. 主函数 backspaceCompare

2. 辅助函数 changeStr

3. 遍历输入字符串

4. 处理字符

5. 返回处理结果

6. 返回比较结果

总结

三、227. 基本计算器 II - 力扣（LeetCode）

算法代码：

1. 初始化变量

2. 遍历字符串

3. 处理空格

4. 处理数字

5. 处理运算符

6. 计算结果

7. 返回结果

总结

四、394. 字符串解码 - 力扣（LeetCode）

算法代码：

1. 初始化栈

2. 遍历输入字符串

3. 处理字符

4. 返回结果

总结

五、946. 验证栈序列 - 力扣（LeetCode）

算法代码：

1. 初始化栈

2. 遍历 pushed 序列

3. 检查弹出条件

4. 返回验证结果

总结

一、1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

算法代码：

class Solution {
public:string removeDuplicates(string s) {string ret; // 搞⼀个数组，模拟栈结构即可for (auto ch : s) {if (ret.size() && ch == ret.back())ret.pop_back(); // 出栈elseret += ch; // ⼊栈}return ret;}
};

1. 初始化结果字符串

结果字符串 ret：用于存储处理后的结果，模拟栈的行为。

2. 遍历输入字符串

字符遍历：使用范围 for 循环逐个访问字符串 s 中的每个字符 ch。

3. 检查和处理字符

判断条件：
- 栈不为空：检查 ret 的大小（ret.size()），如果不为零，表示栈中有元素。
- 相邻字符比较：如果当前字符 ch 与 ret 中的最后一个字符（ret.back()）相同，说明发现了相邻的重复字符。
  - 出栈：使用 pop_back() 方法移除 ret 中的最后一个字符，相当于“出栈”操作。
- 入栈：如果当前字符 ch 不与最后一个字符相同，或者 ret 为空，说明没有重复字符，将该字符追加到 ret 中（ret += ch），相当于“入栈”。

4. 返回结果

最终结果：当所有字符都处理完毕后，ret 中存储的就是移除了所有相邻重复字符的结果，直接返回这个字符串。

总结

该算法通过模拟栈的结构，有效地处理了相邻的重复字符。时间复杂度为 O(n)，其中 n 是字符串 s 的长度，因为每个字符最多只被访问和处理两次（入栈和出栈）。这种方法简单且高效，适合快速移除字符串中的相邻重复字符。

二、844. 比较含退格的字符串 - 力扣（LeetCode）

算法代码：

class Solution {
public:bool backspaceCompare(string s, string t) {return changeStr(s) == changeStr(t);}string changeStr(string& s) {string ret; // ⽤数组模拟栈结构for (char ch : s) {if (ch != '#')ret += ch;else {if (ret.size())ret.pop_back();}}return ret;}
};

1. 主函数 `backspaceCompare`

比较结果：调用 changeStr(s) 和 changeStr(t) 来处理两个字符串，并比较它们是否相等。

2. 辅助函数 `changeStr`

初始化结果字符串 ret：用于存储处理后的字符串，模拟栈的行为。

3. 遍历输入字符串

字符遍历：使用范围 for 循环逐个访问字符串 s 中的每个字符 ch。

4. 处理字符

判断字符：
- 如果当前字符 ch 不是 #，则将其添加到结果字符串 ret 中（ret += ch），表示保留这个字符。
- 如果当前字符是 #，则：
  - 检查 ret 是否为空（ret.size()）。如果不为空，说明可以安全地删除最后一个字符，调用 pop_back() 删除 ret 中的最后一个字符。

5. 返回处理结果

最终结果：当所有字符都处理完毕后，返回处理后的字符串 ret，即字符串 s 在考虑回退字符后得到的结果。

6. 返回比较结果

比较处理后的字符串：在 backspaceCompare 函数中，比较两个处理后的字符串是否相等。

总结

该算法使用模拟栈的方式有效地处理了字符串中的回退操作。两次遍历字符串 s 和 t，每个字符最多访问和处理一次，因此时间复杂度为 O(n + m)，其中 n 和 m 是两个字符串的长度。这种方法简洁且高效，适合在处理带有回退操作的字符串比较时使用。

三、227. 基本计算器 II - 力扣（LeetCode）

算法代码：

class Solution {
public:int calculate(string s) {vector<int> st; // ⽤数组来模拟栈结构int i = 0, n = s.size();char op = '+';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;elsest.back() /= tmp;} else {op = s[i];i++;}}int ret = 0;for (auto x : st)ret += x;return ret;}
};

1. 初始化变量

栈 st：使用一个 vector<int> 来模拟栈结构，存储操作数。
索引 i：初始化为 0，用于遍历字符串 s。
运算符 op：初始化为 '+'，表示当前的运算符。

2. 遍历字符串

循环条件：使用 while (i < n) 遍历整个字符串，直到所有字符都被处理完。

3. 处理空格

跳过空格：如果当前字符是空格，直接将索引 i 加一，继续检查下一个字符。

4. 处理数字

提取数字：如果当前字符是数字（在 '0' 到 '9' 之间），使用一个 while 循环来提取完整的数字。通过将 tmp 乘以 10 并加上当前数字的值 (s[i] - '0') 来构建这个数字。
根据运算符处理数字：
- 如果 op 是 '+'，将 tmp 添加到栈中。
- 如果 op 是 '-'，将 -tmp 添加到栈中（表示减去这个数）。
- 如果 op 是 '*'，将栈顶元素（最后一个数字）与 tmp 相乘，并更新栈顶元素的值。
- 如果 op 是 '/'，将栈顶元素与 tmp 相除，并更新栈顶元素的值。

5. 处理运算符

更新运算符：如果当前字符是运算符（+, -, *, /），将 op 更新为当前字符，索引 i 加一。

6. 计算结果

求和：遍历栈 st，将所有元素累加到结果变量 ret 中。

7. 返回结果

返回最终结果：返回计算得到的结果 ret。

总结

这个计算器的设计通过使用栈结构有效地处理了四则运算的优先级，特别是乘法和除法的优先级高于加法和减法。时间复杂度为 O(n)，其中 n 是字符串的长度，因为每个字符最多只被访问和处理一次。这种方法简洁高效，适合处理没有括号的简单数学表达式的计算。

四、394. 字符串解码 - 力扣（LeetCode）

算法代码：

class Solution {
public:string decodeString(string s) {stack<int> nums;stack<string> st;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');i++;}nums.push(tmp);} else if (s[i] == '[') {i++; // 把括号后⾯的字符串提取出来string tmp = "";while (s[i] >= 'a' && s[i] <= 'z') {tmp += s[i];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];i++;}st.top() += tmp;}}return st.top();}
};

1. 初始化栈

数字栈 nums：用于存储括号前的重复次数。
字符串栈 st：用于存储当前构建的字符串。在开始时，将一个空字符串推入栈中。

2. 遍历输入字符串

索引变量 i：用于遍历字符串 s，初始化为 0，n 为字符串的长度。

3. 处理字符

数字处理：
- 如果字符是数字（在 '0' 到 '9' 之间），需要提取完整的数字。使用一个 while 循环来处理可能为多位数的数字，然后将提取出的数字推入 nums 栈中。
左括号处理：
- 如果遇到 '['，说明要开始一个新的重复段。在此之前需要将当前构建的字符串（即 st 栈顶）推入栈中，然后开始从 '[' 后面提取字符串（直到下一个右括号 ']'）。
- 使用 while 循环提取后续的字母字符，直到遇到非字母字符（此时 i 应该指向右括号或下一个数字），将提取出的字符串推入 st 栈中。
右括号处理：
- 当遇到 ']' 时，从 st 栈中弹出字符串（这就是在这个括号内的字符串），并从 nums 栈中弹出数字（这是重复的次数）。
- 使用一个 while 循环将弹出的字符串重复 k 次，然后将其添加到 st 栈顶的字符串中。
普通字母处理：
- 如果字符是字母（不在数字和括号内），则使用一个 while 循环提取连续的字母，并将其添加到 st 栈顶的字符串中。

4. 返回结果

最终结果：遍历完所有字符后，st 栈顶保存的就是解码后的完整字符串，返回 st.top()。

总结

该算法使用了两个栈来有效地处理字符串的解码。时间复杂度为 O(n)，其中 n 是字符串的长度，因为每个字符最多被访问和处理两次。该方法能够简单、清晰地处理包含嵌套结构的字符串解码问题，适合需要解析类似格式的字符串的场景。

五、946. 验证栈序列 - 力扣（LeetCode）

算法代码：

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