【算法题】栈-深圳市維司達科技有限公司

栈是一种“后进先出（LIFO）”的线性数据结构，核心优势是高效处理“匹配、抵消、嵌套”类问题。在字符串处理（去重、回退、解码）、表达式计算、栈序列验证等场景中，栈能将复杂的顺序逻辑简化为直观的入栈/出栈操作。本文通过5道经典题目，拆解栈在不同场景下的解题思路与代码实现。

一、删除字符串中的所有相邻重复项

题目描述：
给定字符串s，反复删除相邻且相同的字符对，直到无法再删除，返回最终字符串（删除操作会重复进行，直到没有相邻重复项）。

示例：

输入：s = "abbaca"，输出："ca"（"bb"删去→"aaca"，"aa"删去→"ca"）

解题思路：
用栈模拟“相邻抵消”过程：

遍历字符串的每个字符：
- 若栈不为空且栈顶字符与当前字符相同，弹出栈顶（抵消重复项）；
- 若栈为空或字符不同，将当前字符入栈。
遍历结束后，栈中剩余字符即为结果。

完整代码：

classSolution{public:stringremoveDuplicates(string s){string ret;// 用string模拟栈，效率更高for(autoch:s){if(ret.size()&&ch==ret.back())ret.pop_back();elseret.push_back(ch);}returnret;}};

复杂度分析：

时间复杂度：O(n)O(n)O(n)，n为字符串长度，每个字符最多入栈/出栈一次。
空间复杂度：O(n)O(n)O(n)，最坏情况（无重复字符）栈存储所有字符。

二、比较含退格的字符串

题目描述：
给定两个字符串s和t，其中'#'表示退格键（删除前一个字符），判断处理后的两个字符串是否相等。

示例：

输入：s = "ab#c", t = "ad#c"，输出：true（均处理为"ac"）
输入：s = "a#c", t = "b"，输出：false（处理后分别为"c"和"b"）

解题思路：
用栈模拟“退格”过程，分别处理两个字符串后比较结果：

定义辅助函数changeStr：遍历字符串，遇到非'#'字符入栈，遇到'#'且栈非空则出栈。
分别处理s和t，比较处理后的字符串是否相等。

完整代码：

classSolution{public:boolbackspaceCompare(string s,string t){returnchangeStr(s)==changeStr(t);}stringchangeStr(string&s){string tmp;// 用string模拟栈for(autoch:s){if(ch!='#')tmp+=ch;else{if(tmp.size())tmp.pop_back();}}returntmp;}};

复杂度分析：

时间复杂度：O(n+m)O(n+m)O(n+m)，n/m分别为s/t的长度，遍历处理两个字符串。
空间复杂度：O(n+m)O(n+m)O(n+m)，存储处理后的两个字符串。

三、基本计算器 II

题目描述：
实现一个基本计算器，计算包含+、-、*、/的字符串表达式的值（表达式不含括号，仅包含非负整数和空格）。

示例：

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

解题思路：
用栈处理“加减延迟计算，乘除立即计算”的优先级逻辑：

初始化栈和运算符op（默认'+'），遍历表达式：
- 跳过空格；
- 遇到数字，解析完整数值tmp；
- 根据当前运算符处理数值：
  - +：数值入栈；
  - -：负数值入栈；
  - *//：弹出栈顶数值，与当前数值计算后重新入栈。
遍历结束后，栈中所有数值求和即为结果。

完整代码：

classSolution{public:intcalculate(string s){vector<int>st;// 用vector模拟栈inti=0,n=s.size();intop='+';// 记录当前运算符，初始为+while(i<n){if(s[i]==' ')i++;// 跳过空格elseif(s[i]>='0'&&s[i]<='9'){// 解析完整数字inttmp=0;while(i<n&&s[i]>='0'&&s[i]<='9')tmp=tmp*10+(s[i++]-'0');// 根据运算符处理if(op=='+')st.push_back(tmp);elseif(op=='-')st.push_back(-tmp);elseif(op=='*')st.back()*=tmp;elsest.back()/=tmp;// 题目保证除数不为0}elseop=s[i++];// 更新运算符}// 求和得到结果intret=0;for(autox:st)ret+=x;returnret;}};

复杂度分析：

时间复杂度：O(n)O(n)O(n)，n为表达式长度，每个字符仅遍历一次。
空间复杂度：O(n)O(n)O(n)，栈存储中间计算结果（最坏情况存储所有加减项）。

四、字符串解码

题目描述：
给定编码字符串（格式如k[encoded_string]，表示将encoded_string重复k次），返回解码后的字符串。

示例：

输入：s = "3[a]2[bc]"，输出："aaabcbc"
输入：s = "3[a2[c]]"，输出："accaccacc"

解题思路：
用两个栈分别存储“重复次数”和“待拼接的字符串”，处理嵌套解码：

初始化数字栈nums和字符串栈st（初始压入空字符串，简化拼接逻辑）；
遍历字符串：
- 遇到数字：解析完整数字，压入nums；
- 遇到'['：解析后续的字母串，压入st；
- 遇到']'：弹出栈顶字符串和重复次数，将字符串重复后拼接到新的栈顶；
- 遇到字母：直接拼接到栈顶字符串。
遍历结束后，栈顶字符串即为结果。

完整代码：

classSolution{public:stringdecodeString(string s){stack<int>nums;// 存储重复次数stack<string>st;// 存储待拼接的字符串st.push("");// 初始空串，避免栈空判断inti=0,n=s.size();while(i<n){if(s[i]>='0'&&s[i]<='9'){// 解析完整数字inttmp=0;while(s[i]>='0'&&s[i]<='9')tmp=tmp*10+(s[i++]-'0');nums.push(tmp);}elseif(s[i]=='['){i++;// 解析[]内的字母串string tmp;while(s[i]>='a'&&s[i]<='z')tmp+=s[i++];st.push(tmp);}elseif(s[i]==']'){// 弹出并重复拼接string tmp=st.top();st.pop();intk=nums.top();nums.pop();while(k--){st.top()+=tmp;}i++;}else{// 直接拼接字母string tmp;while(s[i]>='a'&&s[i]<='z')tmp+=s[i++];st.top()+=tmp;}}returnst.top();}};

复杂度分析：

时间复杂度：O(L)O(L)O(L)，L为解码后字符串的总长度（重复拼接的总操作数）。
空间复杂度：O(L)O(L)O(L)，栈存储中间字符串和数字。

五、验证栈序列

题目描述：
给定两个整数序列pushed和popped，判断是否可以通过对pushed执行入栈操作，按popped的顺序执行出栈操作。

示例：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]，输出：true
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]，输出：false

解题思路：
模拟栈的入栈/出栈过程：

遍历pushed数组，将元素依次入栈；
每次入栈后，检查栈顶是否与popped的当前元素匹配：
- 若匹配，弹出栈顶，popped指针后移；
遍历结束后，若popped指针遍历完所有元素，说明序列合法。

完整代码：

classSolution{public:boolvalidateStackSequences(vector<int>&pushed,vector<int>&popped){stack<int>st;inti=0,n=popped.size();for(autox:pushed){st.push(x);// 尽可能出栈while(st.size()&&popped[i]==st.top()){st.pop();i++;}}returni==n;// 所有出栈操作完成则合法}};