leetcode 面试经典 150 题：有效的括号

链接	有效的括号
题序号	20
题型	字符串
解法	栈
难度	简单
熟练度	✅✅✅

题目

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([])”
输出：true

提示：
1 <= s.length <= 10⁴
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）：返回栈中元素的数量。
栈可以用数组或链表来实现。数组实现的栈在空间上是连续的，而链表实现的栈在空间上可以是非连续的。
栈的应用场景：
- 函数调用：在函数调用时，系统会将函数的参数、返回地址以及局部变量压入栈中，函数执行完毕后，这些信息会被弹栈。
- 递归：递归函数的每次调用都会创建一个新的栈帧，用于存储局部变量和参数。
- 括号匹配：检查代码中的括号是否正确匹配，可以使用栈来存储遇到的开括号，并在遇到闭括号时检查是否匹配。
- 表达式求值：在计算表达式时，可以使用栈来存储操作数和操作符，以正确计算表达式的值。
- 回溯算法：在搜索和图算法中，栈可以用来存储路径，以便在需要时回溯到上一个状态。
栈是一种非常基础且重要的数据结构，它在计算机科学和软件开发中有着广泛的应用。