有效的括号（字节面试题最优解）

题目来源

20. 有效的括号 - 力扣（LeetCode）

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

题目限制

要求最优解

不能暴力

思路分析

这题可以用栈这种数据结构来解决，以下是思路提示：

首先，遍历给定的字符串。

当遇到左括号（也就是 '('、'{'、'[' 这几种）的时候，把它们依次压入栈中。因为后续要靠它们来匹配对应的右括号嘛。

而一旦遇到右括号（')'、'}'、'[' ）时，就去检查栈顶元素。如果栈为空，那说明没有可以匹配的左括号了，直接返回 false ；要是栈不为空，就看看栈顶的左括号和当前遇到的右括号是不是同一类型的（比如栈顶是 '('，当前是 ')' ，这就是同一类型能匹配上的情况），如果是同一类型，那就把栈顶元素弹出，表示这个括号对匹配上了；要是类型不同，那就不符合要求，直接返回 false 。

最后，当整个字符串都遍历完了，如果栈为空，那就说明所有括号都匹配上了，字符串是有效的，返回 true，要是栈里还有元素，那就意味着有左括号没匹配到右括号，返回 false 。

利用栈来处理的好处在于它能很好地按照顺序来记录和匹配括号，符合括号匹配的先后顺序规则，时间复杂度相对比较优哦。大家可以顺着这个思路再详细去思考具体的实现啦。

具体代码

class Solution {
public:bool isValid(string s) {stack <char> a;for(auto i:s){if(i=='('||i=='{'||i=='[')a.push(i);else {if(a.empty())return false;else{char top=a.top();if((top=='('&&i==')')||(top=='{'&&i=='}')||(top=='['&&i==']'))a.pop();else{return false;}}}}return a.empty();}
};

在上述代码中，我们使用了std::stack（栈）这个容器来辅助我们解决问题。首先，我们遍历输入的字符串 s。当遇到左括号（'('、'{'、'['）时，我们将其压入栈 a 中。而当遇到右括号时，我们首先检查栈是否为空，如果为空，那就意味着没有对应的左括号来匹配这个右括号，所以直接返回 false。如果栈不为空，我们获取栈顶元素 top，然后检查栈顶的左括号和当前的右括号是否是匹配的类型（例如 '(' 和 ')' 匹配、'[' 和 ']' 匹配、'{' 和 '}' 匹配），如果是匹配的，我们就将栈顶元素弹出，表示这一对括号已经成功匹配；如果不匹配，那么就说明字符串中的括号不是有效的，直接返回 false。当整个字符串都遍历完后，如果栈为空，那就说明所有的括号都找到了对应的匹配括号，字符串是有效的，返回 true；否则返回 false。

这种利用栈来解决括号匹配问题的方法，充分利用了栈的后进先出（LIFO）特性，能够高效且准确地判断字符串中括号的有效性。通过这个问题，我们不仅加深了对栈数据结构的理解，也提升了我们解决实际编程问题的能力。

注意事项

解题思路在编程学习中占据着举足轻重的地位。就拿本题来说，关键在于确定运用何种算法予以攻克。多数人起初往往只会盲目地尝试各种括号匹配方式，然而这毫无成效。若无法洞悉解题的核心思路，个人的编程能力将永远停滞不前。刷题的意义绝非仅仅局限于用代码实现某个题目，更为关键的是要深刻领悟其背后的解题思路，而这其中的核心要素便是算法。它宛如一盏明灯，能够穿透问题的重重迷雾，引导我们找到高效且准确的解决方案，从而在编程的学习之路上实现真正的成长与突破。