LeetCode第20题有效的括号

继续打卡算法题，今天学习的是LeetCode的第20题有效的括号，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些帮助。

分析一波题目

这个题目需要判断括号是有效果的，有效括号有一个特征非常重要, 那就是遇到了右边的括号，一定存在左边匹配的括号。

比如[()], 遇到)的时候，最近的一个一定存在(，最近的也是最近最后遍历到的括号，我们可以使用栈结构来表达这种数据。

编码解决

class Solution {
   
   
    public boolean isValid(String s) {
   
   
        int n = s.length();
        //存储关系
        Map<Character, Character> map = new HashMap<Character, Character>() {
   
   {
   
   
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
   
   
            char ch = s.charAt(i);
            //是右边的括号
            if (map.containsKey(ch)) {
   
   
                //是否栈顶有匹配的左边括号
                if (stack.isEmpty() || stack.peek() != map.get(ch)) {
   
   
                    return false;
                }
                stack.pop();
            } else {
   
   
                //左边的括号，入栈
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

总结

栈的先进后出结构可以解决一些有规律的符号匹配的问题，使用起来非常巧妙。