LeetCode 有效的括号题解（栈）

在 LeetCode 中，“有效的括号”是一道经典且常见的算法题。解决这道题的关键在于巧妙地运用数据结构——栈。

让我们来理解一下题目。给定一个只包含括号 '('、')'、'{'、'}'、'[' 和 ']' 的字符串，我们需要判断这个字符串中的括号是否是有效的。所谓有效的括号，是指每个左括号都能找到与之对应的右括号，并且它们的顺序是正确的。

使用栈来解决这个问题的思路非常清晰。我们遍历输入的字符串。当遇到左括号时，将其压入栈中。当遇到右括号时，我们检查栈顶元素。如果栈为空，说明没有与之对应的左括号，直接返回无效。如果栈顶元素不是对应的左括号，也返回无效。只有当栈顶元素是对应的左括号时，我们将其弹出栈。

在遍历完整个字符串后，如果栈为空，说明所有的括号都匹配成功，字符串是有效的；否则，字符串是无效的。

以下是使用 Java 实现的代码示例：

import java.util.Stack;

public class ValidParentheses {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top!= '(') || (c == ']' && top!= '[') || (c == '}' && top!= '{')) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        ValidParentheses validParentheses = new ValidParentheses();
        String s1 = "()";
        String s2 = "()[]{}";
        String s3 = "(]";

        System.out.println(validParentheses.isValid(s1)); 
        System.out.println(validParentheses.isValid(s2)); 
        System.out.println(validParentheses.isValid(s3)); 
    }
}

这种使用栈的方法时间复杂度为 O(n)，空间复杂度也为 O(n)，其中 n 是输入字符串的长度。因为我们只需要对字符串进行一次遍历，并且栈的大小最多与字符串长度相等。

通过这个题，我们可以深刻地理解栈这种数据结构在解决匹配问题上的强大作用。希望这种题解思路能帮助您在 LeetCode 的算法世界中更上一层楼。