20-有效的括号

题目地址(20. 有效的括号 - 力扣（LeetCode）)

https://leetcode.cn/problems/valid-parentheses/description/

题目描述

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

有效字符串需满足：

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

前置知识

• 栈
• 字符串

思路

当我们遇到一个左括号时，就放入一个对应的右括号。

当我们遇到一个右括号时，

• 如果栈为空或者栈顶元素与「当前的右括号」不一样时，那么字符串就是无效的。

• 如果与栈顶元素一样，就说明括号右效。将栈顶元素出栈

最后再判断栈是不是为空，解决 [({}) 这种情况

关键点

• 入栈是右括号，并将当前元素与栈顶元素判断是否相同

代码

• 语言支持：Java

Java Code:

class Solution {
    public boolean isValid(String s) {
        if (s.isEmpty()) {
            return true;
        }
        // 长度为奇数时
        if(s.length() % 2 == 1){
            return false;
        }
        Deque<Character> queue = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if(c == '('){
                queue.offer(')');
            }else if(c == '['){
                queue.offer(']');
            }else if(c == '{'){
                queue.offer('}');
            }else if(queue.isEmpty() || c != queue.pollLast()){
                return false;
            }
        }
        return queue.isEmpty();
    }
}

复杂度分析

令 n 为字符串长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$,创建一个双端队列存放右括号，最多是1/2 n个。