leetcode 面试经典 150 题：有效的括号
| 链接 | 有效的括号 |
|---|---|
| 题序号 | 20 |
| 题型 | 字符串 |
| 解法 | 栈 |
| 难度 | 简单 |
| 熟练度 | ✅✅✅ |
题目
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([])”
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
题解
- 核心思想：判断括号是否有效，关键在于匹配。我们需要确保每个左括号都能找到对应的右括号，并且它们的顺序是正确的。为此，可以使用栈（Stack）来实现。
- 栈（stack）：
- 栈是一种后进先出（LIFO）的数据结构，适合处理括号匹配的问题。
- 每当遇到左括号时，将其压入栈中。
- 每当遇到右括号时，检查栈顶是否为匹配的左括号。
- 复杂度：时间复杂度为O(n)，其中 n 是字符串 s 的长度。空间复杂度为O(n)，由栈的大小决定，哈希表的空间是常数项，因为常数项在大O表示法中是可以忽略的。这意味着算法的空间需求主要取决于输入数据的大小，而与字符集的大小无关。
- c++ 实现算法：
bool isValid(string s) {
// 用栈保存未匹配的左括号
stack<char> st;
// 使用哈希表存储括号的映射关系
//键（Key）：右括号，包括 ')'、']' 和 '}'。
//值（Value）：对应的左括号，包括 '('、'[' 和 '{'。
unordered_map<char, char> brackets = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
// 如果是右括号
//在 unordered_map 中，count(key) 用于检查给定的 键key 是否存在于哈希表中
//如果 key 存在，返回 1. 如果 键key 不存在，返回 0
if (brackets.count(c)) {
// 栈顶字符与右括号的匹配
//检查栈是否为空，或者栈顶是否与当前右括号的匹配左括号相同
//通过 brackets[c] 找到右括号对应的左括号，如果 c 是 ')'，brackets[c] 就是 '('。
if (!st.empty() && st.top() == brackets[c]) {
st.pop(); // 匹配成功，移除栈顶
}
else {
return false; // 匹配失败
}
}
else {
// 如果是左括号，入栈
st.push(c);
}
}
// 栈为空表示所有括号都匹配成功
return st.empty();
}
- 算法推演：
以输入 s = “{[()]}” 为例：
- 遍历字符 ‘{’：入栈 st = [‘{’]。
- 遍历字符 ‘[’：入栈 st = [‘{’, ‘[’]。
- 遍历字符 ‘(’：入栈 st = [‘{’, ‘[’, ‘(’]。
- 遍历字符 ‘)’： 栈顶为 ‘(’，匹配成功，弹出栈顶 st = [‘{’, ‘[’]。
- 遍历字符’]‘： 栈顶为 ‘[’，匹配成功，弹出栈顶 st = [’{']。
- 遍历字符 ‘}’： 栈顶为 ‘{’，匹配成功，弹出栈顶 st = []。
遍历结束，栈为空，返回 true。
- c++ 完整demo：
#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>
using namespace std;
bool isValid(string s) {
// 用栈保存未匹配的左括号
stack<char> st;
// 使用哈希表存储括号的映射关系
//键（Key）：右括号，包括 ')'、']' 和 '}'。
//值（Value）：对应的左括号，包括 '('、'[' 和 '{'。
unordered_map<char, char> brackets = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
// 如果是右括号
//在 unordered_map 中，count(key) 用于检查给定的 键key 是否存在于哈希表中
//如果 key 存在，返回 1. 如果 键key 不存在，返回 0
if (brackets.count(c)) {
// 栈顶字符与右括号的匹配
//检查栈是否为空，或者栈顶是否与当前右括号的匹配左括号相同
//通过 brackets[c] 找到右括号对应的左括号，如果 c 是 ')'，brackets[c] 就是 '('。
if (!st.empty() && st.top() == brackets[c]) {
st.pop(); // 匹配成功，移除栈顶
}
else {
return false; // 匹配失败
}
}
else {
// 如果是左括号，入栈
st.push(c);
}
}
// 栈为空表示所有括号都匹配成功
return st.empty();
}
int main() {
string s = "{[()]}";
if (isValid(s)) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
数据结构之 { 栈 }
- 数据结构中的栈（Stack）是一种遵循“后进先出”（Last In First Out，简称LIFO）原则的有序集合。这意味着最后添加到栈中的元素会首先被移除。栈通常用于处理递归调用、函数调用、表达式求值、括号匹配等场景。
- 栈的基本操作包括：
- 压栈（Push）：将一个元素添加到栈的顶部。
- 弹栈（Pop）：移除并返回栈顶部的元素。
- 查看栈顶元素（Peek 或 Top）：返回栈顶部的元素但不移除它。
- 检查栈是否为空（IsEmpty）：检查栈中是否有元素，如果有返回false，否则返回true。
- 获取栈的大小（Size）：返回栈中元素的数量。
- 栈可以用数组或链表来实现。数组实现的栈在空间上是连续的，而链表实现的栈在空间上可以是非连续的。
- 栈的应用场景：
- 函数调用：在函数调用时，系统会将函数的参数、返回地址以及局部变量压入栈中，函数执行完毕后，这些信息会被弹栈。
- 递归：递归函数的每次调用都会创建一个新的栈帧，用于存储局部变量和参数。
- 括号匹配：检查代码中的括号是否正确匹配，可以使用栈来存储遇到的开括号，并在遇到闭括号时检查是否匹配。
- 表达式求值：在计算表达式时，可以使用栈来存储操作数和操作符，以正确计算表达式的值。
- 回溯算法：在搜索和图算法中，栈可以用来存储路径，以便在需要时回溯到上一个状态。
- 栈是一种非常基础且重要的数据结构，它在计算机科学和软件开发中有着广泛的应用。