当前位置：首页 > news >正文

栈(LIFO)算法题

news 来源：原创 2025/8/15 1:34:54

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

注意，我们需要重复处理，而不是处理一次相邻的相同元素就结束了。对示例来说，如果只进行一次处理，结果为aaca，但是处理之后又出现了相邻的重复元素，我们还得继续处理，最后结果就是ca。

解法：借助栈来模拟

我们可以将字符串中的元素依次入栈，元素入栈前判断是否与栈顶元素相等，如果相等就弹出栈顶元素，继续判断下一个元素。等到字符串全部入栈，栈中的就是最终答案。

但是我们没有必要弄一个stack出来，因为这样最终结果是逆序的，我们可以采用string来模拟栈的行为。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution 
{
public:string removeDuplicates(string s) {// 用string模拟栈string ret;for(auto e : s){if(ret.size() && ret.back() == e) ret.pop_back();else ret.push_back(e);}return ret;}
};

2.比较含退格的字符串

解法1：使用栈来模拟

我们可以封装一个函数出来，用来处理字符串中的退格符。然后比较处理之后的字符串即可。而处理字符串的过程，就可以使用栈来模拟，如果不是#就入栈，如果遍历到#就弹出栈顶元素。这一步依旧可以采取string模拟，避免reverse。

时间复杂度：O(n+m)，n和m分别为s，t的长度，遍历两个字符串各一次

空间复杂度：O(m+n)，处理字符串时，最坏情况下两者都没有退格符

bool _backspaceCompare(string s, string t) 
{return reBulidString(s) == reBulidString(t);
}string reBulidString(string str)
{string ret;for(auto e : str){if(e == '#' && ret.size()) ret.pop_back();else if(e != '#') ret.push_back(e);}return ret;
}

解法2：双指针

因为退格符只会对前面的字符产生影响，所以我们可以逆序遍历字符串。我们分别定义skipS和skipT来记录当前的退格次数。如果如果#则skipS++，如果遍历到普通字符，则看skipST是否为0，如果为0，则表示这个字符肯定会留下来，接着就去遍历t字符串，找到一个不会被删除的字符，然后判断这两个字符是否相等。如果不相等，则返回false；如果一个字符串为空了，另一个还有，则也返回false。

但是有一种情况需要注意，如果两个字符串最后一个字符是#，或者最后一个字符被删除了，此时两者都越界了，此时返回true。

时间复杂度：O(m+n)

空间复杂度：O(1)

    bool backspaceCompare(string s, string t) {int i = s.size() - 1, j = t.size() - 1;int skipS = 0, skipT = 0;while(i >= 0 || j >= 0) // 这里为什么是或{// 在S中寻找不会被删除的字符while(i>=0){if(s[i] == '#') skipS++, i--;else if(skipS) skipS--, i--;else break; // 退出该循环说明当前这个字符不会被删除}// 在T中寻找不会被删除的字符while(j>=0){if(t[j] == '#') skipT++, j--;else if(skipT) skipT--, j--;else break; // 当前字符不会被删除}if(i>=0 && j>=0){if(s[i] != t[j]) return false;}else if(i>=0 || j>=0) return false;i--, j--;}return true;}

3.基本计算器2

解法：栈模拟

我们有可能会遇到空格，数字或者运算符，因为优先级的原因，我们如果遇到+/-时不能直接计算，我们采取的策略是将其先放入到栈中，为了避免+/-的运算不同，所以如果是+号，则直接存储到栈中，如果是-号，则将其相反数压入栈中。这样栈中的元素只需要进行加法运算即可。

如果遇到乘号或者除法，则我们直接将后面的数乘或除到栈顶元素上。等遍历完字符串后，直接将栈中的元素加起来即可。

需要注意的是，数字并不只是一位数，所以我们在遇到数字，需要将后面的数字也提取出来，并且要注意位数。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution 
{
public:int calculate(string s) {   stack<int> calc;// 处理运算符char option = '+'; //第一个数前面的运算符被视为加号for (int i = 0; i < s.size();){// 处理空格if(s[i] == ' '){i++;}else if(isdigit(s[i]))//先获取数字，数字可能是多位数{int tmp = 0;while(i<s.size() && isdigit(s[i])){tmp = tmp*10 + (s[i++]-'0');}//判断该数前面的符号是什么// 加减直接将数字压入栈中，减法压入负数// 乘除让栈顶数据*= / /= 上当前的数字if(option == '+') calc.emplace(tmp);else if(option == '-') calc.emplace(-tmp);else if(option == '*') calc.top() *= tmp;else calc.top() /= tmp;}else // 如果是操作符，则更新操作符{option = s[i];i++;}}// 栈中的元素使用加法计算即可int ret = 0;while (!calc.empty()){ret += calc.top();calc.pop();}return ret;}
};

4.字符串解码

我们在进行解码的时候要从最内部开始解码，因为最外层的方括号内部可能还嵌套这其他方括号。

解法：栈+分类讨论

我们在遍历字符串的时候，可能遇到数字，左方括号，右方括号，和字母。而我们要分别存储数字和字母，所以借助两个栈来实现。

如果遇到数字，我们就提取该数字，因为可能是多位数，所以要循环提取，然后将该数压入到数字栈中。

如果遇到了左括号，我们接下来就提取字符串，然后压入到字符栈中。

如果遇到了右括号，说明这是最内层的，此时就可以进行解析。解析之后，我们还得将该结果接到栈顶元素的后面。

如果遇到了字母，则提取该字母，因为该字母并没有出现在括号中，所以没有进行重复，直接插入到栈顶元素的后面即可。

细节：因为字符栈有可能为空，这时向栈顶元素后面加上字符就会报错。所以我们可以提前给栈顶元素压入一个空串。避免这种情况。

时间复杂度：O(S)，除了遍历原字符串，每一次解码都会将其连接到栈顶元素。

空间复杂度：O(S)，解码后的字符串长度

class Solution
{
public:string decodeString(string s){stack<int> nst;stack<string> sst;sst.emplace("");int i = 0, n = s.size();while (i < n){// 1.如果遇到数字，则提取数字放入数字栈中if (isdigit(s[i])){int tmp = 0;while (i < n && isdigit(s[i]))tmp = tmp * 10 + (s[i++] - '0');nst.emplace(tmp);}// 2.如果是左括号，则提取左括号后面的字符串else if (s[i] == '['){i += 1;string t;while (i < n && s[i] <= 'z' && s[i] >= 'a')t += s[i++];sst.emplace(t);}// 3.如果是右括号，则拿出两个栈的栈顶进行解析，并将解析后的结果接到sst栈顶的后面else if (s[i] == ']'){//解析string t;int count = nst.top();nst.pop();while (count--) t += sst.top();sst.pop();//更新sst.top() += t;i++;// 遍历下一个位置}// 4.如果直接遇到字母，则直接加到字符栈顶元素的后面else{string t;while (i < n && s[i] <= 'z' && s[i] >= 'a')t += s[i++];sst.top() += t;}}return sst.top();}
};

5.验证栈序列

这道题在学习栈的时候是经常会遇到的一道题，判断入栈顺序能否满足出栈顺序。

解法：模拟

我们按照入栈顺序进行入栈，然后判断栈顶元素与出栈元素是否相等，如果相等，则出栈，然后指针指向下一个出栈元素。如果不相等，则继续入栈。

如果最后栈为空，则说明满足，否则不满足。

时间复杂度：O(n)

空间复杂度：O(n)

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

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

2.比较含退格的字符串

3.基本计算器2

4.字符串解码

5.验证栈序列

相关文章：