20. 有效的括号
3 min
题目
思路
核心思想是使用栈进行括号匹配：遇到左括号入栈，遇到右括号则检查栈顶左括号是否与之匹配。
正确性在于栈的先进后出特性完美模拟括号的嵌套结构：当遇到右括号时，只有最近未匹配的左括号（栈顶）才能与之配对，因为括号闭合必须遵循后进先出顺序。若栈顶括号类型不匹配或栈为空（右括号多余），则立即返回无效；遍历结束后栈必须为空（左括号无多余）。
- Step 1: 初始化栈和括号映射表（左括号→右括号）
- Step 2: 遍历字符串，若字符是左括号则入栈
- Step 3: 若字符是右括号，检查栈顶左括号是否匹配：匹配则弹出，否则返回false
- Step 4: 遍历结束后，栈为空则返回true，否则false
复杂度
- 时间复杂度: ，其中为字符串长度。每个字符仅遍历一次，栈操作均为。
- 空间复杂度: ，最坏情况下（如全为左括号）栈需存储整个字符串。
代码
class Solution {
public:
bool isValid(string s) {
stack<char>stk;
map<char,char>mp;
mp['('] = ')';mp['{'] ='}';mp['['] = ']';
for(auto i:s){
if(stk.empty()){
if(!mp[i])
return false;
else
stk.push(i);
}
else{
if(mp[i]){
stk.push(i);
}
else{
if(mp[stk.top()] == i){
stk.pop();
}
else
return false;
}
}
class Solution {
public:
bool isValid(string s) {
stack<char>stk;
map<char,char>mp;
mp['('] = ')';mp['{'] ='}';mp['['] = ']';
for(auto i:s){
if(stk.empty()){
if(!mp[i])
return false;
else
stk.push(i);
}
else{
if(mp[i]){
stk.push(i);
}
else{
if(mp[stk.top()] == i){
stk.pop();
}
else
return false;
}
}
}
if(stk.empty())
return true;
else
return false;
}
};