有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s。

判断字符串是否有效。

有效字符串需要满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([])"
输出：true

示例 5：

输入：s = "([)]"
输出：false

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

栈：

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;
                }

                char top = st.top();
                st.pop();

                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{'))
                {
                    return false;
                }
            }
        }

        return st.empty();
    }
};

核心思想

这题要求括号不仅类型匹配，还必须按照正确顺序闭合。

最直接的想法是从左到右扫描字符串。

遇到左括号时，它暂时还没有被匹配，需要先保存起来。

遇到右括号时，它必须匹配最近一个还没有闭合的左括号。

这正好符合栈的特点：

后出现的左括号，必须先被匹配。

也就是“后进先出”。

因此使用栈保存还没有匹配的左括号。

每遇到一个右括号，就检查栈顶左括号是否和它是同一类型。

栈中存什么

栈中只保存还没有匹配的左括号：

stack<char> st;

遇到左括号：

st.push(c);

表示当前左括号等待之后的右括号来闭合。

遇到右括号时，需要拿栈顶元素来匹配。

因为栈顶就是最近出现、还没有被匹配的左括号。

匹配逻辑

当遇到右括号时，先判断栈是否为空。

如果栈为空，说明前面没有任何左括号可以和当前右括号匹配：

if (st.empty())
{
    return false;
}

如果栈不为空，就取出栈顶左括号：

char top = st.top();
st.pop();

然后判断类型是否匹配：

(c == ')' && top != '(')
(c == ']' && top != '[')
(c == '}' && top != '{')

只要有一种不匹配，就说明字符串无效，返回 false。

如果匹配成功，就继续扫描后面的字符。

为什么最后要判断栈为空

扫描结束后，如果栈为空，说明所有左括号都已经被匹配。

如果栈不为空，说明还有左括号没有右括号闭合。

例如：

s = "(()"

扫描结束后，栈中还剩一个 '('。

所以这个字符串不是有效括号字符串。

因此最终返回：

return st.empty();

为什么不能只统计数量

只统计每种括号的数量是不够的。

例如：

s = "([)]"

它包含：

• 一个 '(' 和一个 ')'
• 一个 '[' 和一个 ']'

数量看起来都匹配。

但是闭合顺序不对。

'[' 是后出现的左括号，应该先用 ']' 闭合。

实际字符串却先出现了 ')'，所以无效。

栈可以准确检查这种“最近左括号必须最先闭合”的顺序要求。

边界情况

如果字符串长度是 1，它只可能是一个单独的左括号或右括号，无法形成有效字符串，算法会返回 false。

如果字符串一开始就是右括号，例如：

s = ")"

此时栈为空，直接返回 false。

如果字符串全是左括号，扫描过程中不会失败，但最后栈不为空，因此返回 false。

如果所有括号都能按正确类型和正确顺序匹配，最后栈一定为空，返回 true。

正确性证明

我们证明：算法返回 true 当且仅当字符串是有效括号字符串。

结论 1：栈中始终保存还没有匹配的左括号

从左到右扫描字符串。

遇到左括号时，算法把它压入栈，表示它等待之后的右括号匹配。

遇到右括号时，算法会弹出栈顶左括号和它匹配。

如果匹配成功，这一对括号就被完整闭合，不需要继续留在栈中。

因此任意时刻，栈中保存的都是已经出现但还没有匹配的左括号。

结论 2：如果算法返回 false，字符串一定无效

算法返回 false 有两种情况。

第一种是遇到右括号时栈为空。

这说明当前右括号没有对应的左括号，违反有效字符串要求。

第二种是栈顶左括号和当前右括号类型不匹配。

由于栈顶是最近出现且尚未闭合的左括号，如果它不能被当前右括号闭合，那么闭合顺序或括号类型一定错误。

所以算法返回 false 时，字符串一定无效。

结论 3：如果字符串无效，算法一定会返回 false

如果某个右括号没有对应的左括号，那么扫描到它时，栈会为空，算法返回 false。

如果某个右括号类型不匹配，扫描到它时，栈顶左括号不是对应类型，算法返回 false。

如果所有右括号扫描时都能匹配，但最后仍有左括号没有闭合，那么扫描结束后栈不为空，算法返回 false。

因此所有无效情况都会被算法发现。

结论 4：如果算法最终返回 true，字符串一定有效

算法最终返回 true 说明扫描过程中没有出现空栈匹配，也没有出现类型不匹配。

同时，最后栈为空，说明所有左括号都被匹配完成。

根据结论 1，每一对括号都是按照最近未闭合左括号与当前右括号匹配的。

所以括号类型和闭合顺序都正确，字符串有效。

得出结论

由结论 2 可知，算法不会把无效字符串误判为有效。

由结论 3 可知，算法不会漏掉任何无效情况。

由结论 4 可知，算法返回 true 时字符串一定满足题意。

因此算法正确。

举例理解

以：

s = "([])"

为例。

扫描过程如下：

最终栈为空，所以返回：

true

再看：

s = "([)]"

扫描到 ')' 时，栈顶是 '['。

')' 不能和 '[' 匹配，所以直接返回：

false

复杂度分析

设字符串长度为 n。

每个字符只会被扫描一次。

每个左括号最多入栈一次，每个匹配到的左括号最多出栈一次。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

空间复杂度来自栈。

在最坏情况下，字符串全部是左括号，栈中会保存 n 个字符。