20. 有效的括号
题目链接/文章讲解/视频讲解：代码随想录
解题思路
我们只需要用栈来解决即可，当遇到左括号，就往栈里添加右括号（方便做匹配）。我们分析一下括号不匹配的情况其实只有三种，随后我们可以在一开始做剪枝操作，当字符串不为偶数时，肯定不匹配
1.左括号多出来了
2.左右括号不匹配
3.右括号多出来了
动画演示（图片均来自代码随想录）
代码实现
class Solution {
public:
bool isValid(string s) {
if(s.size()%2 != 0) return false; //剪枝操作
stack<char> st;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(') st.push(')');
else if(s[i]=='{') st.push('}');
else if(s[i]=='[') st.push(']'); //三种情况
else if(st.empty()||s[i]!=st.top()) return false; //第二和第三种情况
else st.pop();
}
return st.empty(); //当遍历完之后还剩元素，说明左括号多了，第一种情况
}
};
时间复杂度：O（n）
空间复杂度：O（n）
总结
栈不仅可以记录出现的元素，还可以记顺序
1047. 删除字符串中的所有相邻重复项
题目链接/文章讲解/视频讲解：代码随想录
解题思路
我们只需要利用栈即可解决问题，因为栈可以帮我们记住遍历的上一个元素是什么，最后消除完后需要颠倒结果，也可以直接用字符串做栈，可以节省时间
class Solution {
public:
string removeDuplicates(string s) {
string result; //用字符串模拟栈，将字符串尾部作为入栈口即可
for(char a:s)
{
if(result.empty()||a!=result.back()) //如果上一个和自己不一样或者空，直接加入
{
result.push_back(a);
}
else
{
result.pop_back(); //不一样直接弹出即可
}
}
return result;
}
};
时间复杂度：O（n）
空间复杂度：O（1）
总结
当遇到相邻匹配的问题时，我们都可以使用栈来解决，因为栈可以帮助我们记录上一个遍历的元素是什么
150. 逆波兰表达式求值
题目链接/文章讲解/视频讲解： 代码随想录
解题思路
这题第一次遇到，直接用栈来解决即可，栈的第三种应用除了前面的相邻字符的匹配，和相连字符的消除，也有类似于这样的后缀表达式的计算，我们只需要遇到数字时入栈，当碰到操作符时，取出两个数操作后，再入栈即可
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> st;
for(int i=0;i<tokens.size();i++)
{
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
{
long long nums1 = st.top(); //先取再弹出，同时用栈求解逆波兰式，我们先取的是右操作数
st.pop();
long long nums2 = st.top();
st.pop();
if(tokens[i]=="+") st.push(nums2+nums1);
if(tokens[i]=="-") st.push(nums2-nums1);
if(tokens[i]=="*") st.push(nums2*nums1);
if(tokens[i]=="/") st.push(nums2/nums1);
}
else
{
st.push(stoll(tokens[i])); //如果不是操作符，就直接入栈，stoll是字符串转long long类型的函数，在string头文件中
}
}
int res = st.top();
st.pop();
return res;
}
};
总结
栈也可以用于逆波兰式的求解，也适用于相邻元素匹配，和相邻元素消除，而逆波兰时在动画上看也是一种消除，因此都是可以用栈来求解的
收获
今天依旧是在旅游，但是打卡不能听，算是勉强跟上，不掉队，加油吧
