本文共 1759 字，大约阅读时间需要 5 分钟。

20.有效的括号

题目

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

思路

运用栈的思想，将左半边的符号压入栈中，只要遇到右半边与之对应的符号，就将其出栈。最终，只要两边完全抵消，就表明括号都是一一对应的，也就是有效的。

• 初始化栈stack
• 依次处理表达式的每个括号。
• 如果遇到左半边括号，推入栈中，稍后处理。
• 如果遇到右半边的括号，检查栈顶的元素是否为对应的左半边括号，如果是，就弹出栈，不是的话，直接无效。
• 最后的最后，如果栈中还有残留，说明表达式存在无效的括号。

代码实现

package leetcode.pac20;import java.util.HashMap;import java.util.Stack;/** * @auther Summerday */public class ValidBrackets {    public static void main(String[] args) {        ValidBrackets validBrackets = new ValidBrackets();        String testString = "(((";        System.out.println(validBrackets.isValid(testString));    }    private HashMap
   
     mappings;    public ValidBrackets() {        this.mappings = new HashMap
    
     ();        this.mappings.put(')', '(');        this.mappings.put(']', '[');        this.mappings.put('}', '{');    }    public boolean isValid(String s) {        //初始化栈        Stack
     
       stack = new Stack
      
       ();        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            //如果遇到右半边的括号的话            if (this.mappings.containsKey(c)) {                //取栈顶元素，如果栈为空，给栈顶元素暂时赋值，不然后面会出现                //EmptyStackException                char topElement = stack.empty() ? '#' : stack.pop();                //栈顶元素和匹配值不相符，直接返回错误                if (topElement != this.mappings.get(c)) {                    return false;                }            } else {                //如果没有遇到右半边的括号，将左半边入栈                stack.push(c);            }        }        //两边完全抵消，即为有效符号        return stack.isEmpty();    }}
      
     
    
   

复杂度分析

• 时间复杂度：O(n)，因为每次只遍历字符串中的一个字符并在栈上进行O(1)的推入和推出操作。n为字符串的字符数量。
• 空间复杂度：O(n),最糟糕的情况，就是全部都是左半边括号，一直往里推，最终把所有的都推进去。同样地，n为左半边的符号的最大数量。