栈LIFO算法题
栈(LIFO)算法题
注意，我们需要重复处理，而不是处理一次相邻的相同元素就结束了。对示例来说，如果只进行一次处理，结果为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;
}
};解法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;
}解法：栈模拟
我们有可能会遇到空格，数字或者运算符，因为优先级的原因，我们如果遇到+/-时不能直接计算，我们采取的策略是将其先放入到栈中，为了避免+/-的运算不同，所以如果是+号，则直接存储到栈中，如果是-号，则将其相反数压入栈中。这样栈中的元素只需要进行加法运算即可。
如果遇到乘号或者除法，则我们直接将后面的数乘或除到栈顶元素上。等遍历完字符串后，直接将栈中的元素加起来即可。
需要注意的是，数字并不只是一位数，所以我们在遇到数字，需要将后面的数字也提取出来，并且要注意位数。
时间复杂度：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;
}
};我们在进行解码的时候要从最内部开始解码，因为最外层的方括号内部可能还嵌套这其他方括号。
解法：栈+分类讨论
我们在遍历字符串的时候，可能遇到数字，左方括号，右方括号，和字母。而我们要分别存储数字和字母，所以借助两个栈来实现。
如果遇到数字，我们就提取该数字，因为可能是多位数，所以要循环提取，然后将该数压入到数字栈中。
如果遇到了左括号，我们接下来就提取字符串，然后压入到字符栈中。
如果遇到了右括号，说明这是最内层的，此时就可以进行解析。解析之后，我们还得将该结果接到栈顶元素的后面。
如果遇到了字母，则提取该字母，因为该字母并没有出现在括号中，所以没有进行重复，直接插入到栈顶元素的后面即可。
细节：因为字符栈有可能为空，这时向栈顶元素后面加上字符就会报错。所以我们可以提前给栈顶元素压入一个空串。避免这种情况。
时间复杂度：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();
}
};这道题在学习栈的时候是经常会遇到的一道题，判断入栈顺序能否满足出栈顺序。
解法：模拟
我们按照入栈顺序进行入栈，然后判断栈顶元素与出栈元素是否相等，如果相等，则出栈，然后指针指向下一个出栈元素。如果不相等，则继续入栈。
如果最后栈为空，则说明满足，否则不满足。
时间复杂度：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();
}
};