【每日算法】有效的括号 LeetCode

public bool IsValid(string s)
    {
        var stack = new Stack<char>();
        foreach (var c in s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                stack.Push(c);
            }
            else
            {
                if (stack.Count == 0)
                {
                    return false;
                }
                var top = stack.Pop();
                if (c == ')' && top != '(')
                {
                    return false;
                }
                if (c == ']' && top != '[')
                {
                    return false;
                }
                if (c == '}' && top != '{')
                {
                    return false;
                }
            }
        }
        return stack.Count == 0;
    }

1. 核心数据结构：栈（Stack）

• 特性：栈是一种 后进先出（LIFO）的数据结构，只允许在栈顶进行插入（ Push ）和删除（ Pop ）操作。
• 为什么用栈？
  括号匹配需要检查最近出现的左括号是否与当前右括号匹配，而栈的 LIFO 特性正好满足这一需求。

2. 算法逻辑分步解析

(1) 遍历字符串

foreach (var c in s)

• 逐个检查字符串中的字符 c 。

(2) 处理左括号

if (c == '(' || c == '[' || c == '{')
{
    stack.Push(c);
}

• 遇到左括号（ ( , [ , { ）时，将其压入栈中，等待后续匹配。

(3) 处理右括号

else
{
    if (stack.Count == 0)
    {
        return false; // 栈为空，说明右括号没有匹配的左括号
    }
    var top = stack.Pop(); // 弹出栈顶的左括号
    if (c == ')' && top != '(')
    {
        return false; // 括号类型不匹配
    }
    // 同理检查其他括号类型...
}

• 关键点：
  • 栈为空：说明当前右括号没有对应的左括号（如 ")" ），直接返回 false 。
  • 类型不匹配：弹出的左括号与当前右括号类型不一致（如 "(]" ），返回 false 。

(4) 最终检查

return stack.Count == 0;

• 栈为空：所有左括号均被匹配，返回 true 。
• 栈非空：存在未匹配的左括号（如 "(" ），返回 false 。

3. 时间复杂度与空间复杂度

• 时间复杂度： O(n)
  只需遍历字符串一次，每个字符的操作（ Push / Pop ）均为 O(1) 。
• 空间复杂度： O(n)
  最坏情况下（如全是左括号 "(((((" ），栈需要存储所有字符。

4. 边界条件处理

• 空字符串：直接返回 true （代码中未显式处理，但逻辑已覆盖）。
• 单字符字符串：如 "(" 或 ")" ，会被正确判断为无效。
• 嵌套括号：如 "([{}])" ，栈会按顺序匹配。

5. 与其他方法的对比

6. 为什么这是最优解？

• 效率：一次遍历即可完成，时间和空间复杂度均为线性。
• 扩展性：只需修改条件即可支持更多括号类型（如 < 和 > ）。
• 鲁棒性：严格处理所有边界条件。

7. 可视化流程（以 "([{}])" 为例）

总结

通过栈的 LIFO 特性高效解决括号匹配问题。理解其核心逻辑后，可以轻松扩展到类似问题（如 HTML 标签匹配、函数调用栈检查等）