太原网站建设晋icp备西安网络科技有限公司
📟作者主页：慢热的陕西人
🌴专栏链接：力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
文章目录
- 牛客热题：有效括号
- 题目链接
- 方法一：栈
- 思路
- 代码
- 复杂度
牛客热题：有效括号
题目链接
有效括号序列_牛客题霸_牛客网 (nowcoder.com)
方法一：栈
思路
入栈：
- 当栈内为空或者栈顶的括号和当前遍历到的括号是不匹配的
出栈：
- 当栈顶的括号和当前遍历到的括号是匹配的情况
代码
stack<char> st;bool check(const char c){if(c == ')' && st.top() == '(') return true;else if(c == ']' && st.top() == '[') return true;else if(c == '}' && st.top() == '{') return true;else return false;}bool isValid(string s) {for(auto c : s){if(!st.empty()){if(!check(c)) st.push(c);else st.pop();}else{st.push(c);} }return st.empty();}
复杂度
时间复杂度：O(N) ,遍历了一遍string
空间复杂度：O(N), 创建了一个栈空间，用于临时存储括号