20.有效的括号

难度：容易

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

括号匹配是使用栈解决的经典问题。

栈先入后出的特点恰好与本题括号排序的特点一致，即：若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 应该为空。

算法流程：

1. 先判断字符串长度是否为奇数，如果字符串长度为奇数，一定不是有效的括号组合，直接返回 false
2. 遍历字符串中的每个字符
   1. 如果字符是开括号，将其推入栈中
   2. 如果栈为空时，此时遇到闭括号，说明括号匹配失败，直接返回 false
   3. 如果栈不为空，此时遇到闭括号，但与栈顶元素（开括号）不匹配，说明括号匹配失败，返回 false
   4. 如果栈不为空，此时遇到闭括号，且与栈顶元素（开括号）匹配，则弹出栈顶元素
3. 已经遍历完了字符串时，
   1. 如果栈为空，说明所有括号都是有效匹配，返回 true
   2. 如果栈不为空，说明有相应的开括号没有对应的闭括号来匹配，所以返回 false

我的代码（使用数组模拟栈）

public boolean isValid(String s) {
    // 获取字符串的长度
    int ls = s.length();
    // 如果字符串长度为奇数，一定不是有效的括号组合
    if (ls % 2 != 0) {
        return false;
    }

    // 创建一个字符数组作为栈
    char[] stack = new char[ls];
    // 初始化栈顶指针
    int top = -1;

    // 遍历字符串中的每个字符
    for (int i = 0; i < ls; i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {// 如果字符是开括号，将其推入栈中
            stack[++top] = c;
        } else if (top == -1) {// 如果栈为空时遇到闭括号，直接返回false
            return false;
        } else if ((c == ')' && stack[top] != '(') ||
                (c == '}' && stack[top] != '{') ||
                (c == ']' && stack[top] != '[')) {// 如果当前闭括号与栈顶开括号不匹配，返回false
            return false;
        } else {// 如果匹配，弹出栈顶元素
            top--;
        }
    }

    // 如果栈为空，说明所有括号都是有效匹配；否则，返回false
    return top == -1;
}

时间复杂度：O(n)

空间复杂度：O(n)

使用 Deque 作为栈的写法

public boolean isValid(String s) {
    // 获取字符串的长度
    int ls = s.length();
    // 如果字符串长度为奇数，一定不是有效的括号组合
    if (ls % 2 != 0) {
        return false;
    }
    // 使用双端队列作为栈
    Deque<Character> stack = new LinkedList<Character>();
    // 遍历字符串中的每个字符
    for (int i = 0; i < ls; i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {// 如果字符是开括号，将其推入栈中
            stack.push(c);
        } else if (stack.isEmpty()) {// 如果栈为空时遇到闭括号，直接返回false
            return false;
        } else if ((c == ')' && stack.peek() != '(') ||
                (c == '}' && stack.peek() != '{') ||
                (c == ']' && stack.peek() != '[')) {// 如果当前闭括号与栈顶开括号不匹配，返回false
            return false;
        } else {// 如果匹配，弹出栈顶元素
            stack.pop();
        }
    }
    // 如果栈为空，说明所有括号都有效匹配；否则，返回false
    return stack.isEmpty();
}

时间复杂度：O(n)

空间复杂度：O(n)

总结

括号匹配是使用栈解决的经典问题。

技巧性的东西没有固定的学习方法，还是要多看多练，灵活运用。