题目分析

“有效的括号”是一个经典的栈应用问题。给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解题思路

解决这个问题的关键在于利用栈这一数据结构，遵循先进后出的原则，来跟踪和匹配每种类型的括号。

处理步骤：

使用栈跟踪括号：遍历给定的字符串，对于每一个字符，如果是左括号则推入栈中，这表示我们期待相对应的右括号出现来匹配它。如果是右括号，则需要检查它是否与栈顶的左括号匹配。
匹配检查：每次遇到右括号时，检查栈是否为空以及栈顶元素是否与之匹配。如果匹配，从栈中弹出栈顶元素；如果不匹配，或栈为空，则直接返回false。
最终栈的状态：在完全遍历字符串后，如果栈为空，则说明所有的括号都正确匹配，返回true；否则，返回false。

Java解法

下面是使用Java语言的解法：

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }
}

不过，这样在代码里面硬编码括号字符，逼格显然是不够的，你必须装的一手好逼，别人才会投来敬仰的眼光。我们立刻改改，把括号提取到一个map中维护：

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        // 使用Map维护左右括号的匹配关系
        Map<Character, Character> map = new HashMap<>();
        map.put('{', '}');
        map.put('[', ']');
        map.put('(', ')');

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                // 如果是左括号，推入栈中
                stack.push(c);
            } else if (stack.isEmpty() || map.get(stack.pop()) != c){
                return false;
            }
        }

        // 完全遍历字符串后，检查栈是否为空来确定是否有效
        return stack.isEmpty();
    }
}

使用映射来维护括号的匹配关系，不仅使代码更加清晰，而且增强了代码的扩展性。

此外，通过栈来处理成对的结构匹配问题是一个常用的技巧。

时间复杂度

O(n)：这里的n代表输入字符串的长度。算法需要遍历整个字符串一次，对于每个字符进行的操作（如检查是否为右括号、匹配栈顶元素、推入或弹出栈等）都可以在常数时间内完成。因此，总的时间复杂度为线性时间复杂度O(n)。

空间复杂度

O(n)：在最坏的情况下（例如全部都是左括号），栈可能需要存储整个字符串中的所有字符，因此空间复杂度为O(n)。

虽然映射（Map）也占用了额外的空间，但其大小是固定的（因为只存储三种括号匹配关系），并且与输入字符串的长度无关，所以映射的空间可以视为常数空间O(1)。因此，总的空间复杂度主要由栈的使用决定，为O(n)。

References

20.有效的括号 ↩︎

趣味算法题

使用栈解决有效的括号问题