$$\color{Red}{有效的括号【leetcode 20 栈】}$$

下面的链接是——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解析

这道题，首先要考虑什么情况下是合法的，当出现左括号的情况下，其实不需要考虑前面有什么括号，但是一旦出现一个左括号，必须后面接别的左括号，或者是和自己类型相同的右括号。

举个例子

已经出现 - > "[({" 的情况下
只能接别的左括号 或者是 "}" 
"[({)" 这种非法
满足嵌套的前提是内层已经产生左右抵消
如 "[({}" 
此时才能接 ")"

同时要满足在上面的前提下，每个左括号都有一个对应的右括号和它抵消。

考虑到一旦抵消，就只需要考虑更外层的情况，同时考虑的是邻居类型，不用考虑更远的情况，这里就可以使用栈来破解这道题，一旦满足能抵消，这两个元素都从栈清除即可。

即：遍历字符串的每个字符

1. 如果是左括号，直接放入栈

2. 如果是右括号，判断栈是否为空

2.1. 为空，直接返回失败

2.2. 不为空，判断是否栈顶和自己是匹配的左括号，不匹配直接返回失败【不可能是右括号，因为如果上一个元素是右括号的情况，如果匹配到左括号就会移除，如果没匹配到会返回失败】

1. 最后返回是否栈元素为空，防止边界情况

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stk = new LinkedList<>();

        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            if (c == '{' || c == '(' || c == '[') stk.push(c);
            else if (!stk.isEmpty() && Math.abs(c - stk.peek()) <= 2) stk.pop();
            else return false;
        }

        return stk.isEmpty();
    }
}