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

最后编辑于2025-07-07

20. 有效的括号（Valid Parentheses）

Easy

给定只包含字符 '(' , ')' , '{' , '}' , '[' , ']' 的字符串 s，判断该字符串是否为有效的括号字符串。有效的定义为：

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

示例：

  • 输入：s = "()" → 输出：true
  • 输入：s = "()[]{}" → 输出：true
  • 输入：s = "(]" → 输出：false

约束：

  • 1 <= s.length <= 10^4
  • s 仅包含字符 '()[]{}'

思路（栈模拟）

这是典型的栈题：遇到左括号就压栈；遇到右括号时检查栈顶是否为匹配的左括号。若不匹配或栈为空则返回 false，遍历结束后若栈为空则为 true，否则为 false。

一个常用的小技巧是：在遇到左括号时，将其对应的右括号压入栈（而不是左括号本身）。这样当遍历到右括号时，直接比较当前字符是否等于栈顶即可，代码更简洁。

解法一：常规栈模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') st.push(c);
            else {
                if (st.empty()) return false;
                if (c == ')' && st.top() != '(') return false;
                if (c == ']' && st.top() != '[') return false;
                if (c == '}' && st.top() != '{') return false;
                st.pop();
            }
        }
        return st.empty();
    }
};

解法二：压入期望的右括号（更简洁）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(') st.push(')');
            else if (c == '{') st.push('}');
            else if (c == '[') st.push(']');
            else {
                if (st.empty() || st.top() != c) return false;
                st.pop();
            }
        }
        return st.empty();
    }
};
  • 时间复杂度： O(n)
  • 空间复杂度： O(n)

作者想说的话：
用栈模拟左右括号匹配是此题最自然的解法。技巧性写法（压入期望的右括号）能让出栈匹配更直接、代码更简洁，但本质的逻辑仍是栈的进出与匹配。