20. 有效的括号

栈

class Solution {
    // public boolean isValid(String s) {
    //     Stack<Character> stack = new Stack<>();
    //     for (int i = 0; i < s.length(); i++) {
    //         char c = s.charAt(i);
    //         if (c == '(' || c == '[' || c == '{') {
    //             stack.push(c);
    //         } else {
    //             if (!stack.isEmpty() && Math.abs(c - stack.peek()) <= 2) {
    //                 stack.pop();
    //             } else {
    //                 return false;
    //             }
    //         }
    //     }
    //     return stack.isEmpty();
    // }

    // List模拟栈
    public boolean isValid(String s) {
        List<Character> list = new ArrayList<>();
        int top = 0;
        for(char ch:s.toCharArray()){
            if(ch=='{'||ch=='['||ch=='('){
                list.add(top++,ch);
            }else{
                if(top==0) return false;
                char c = list.remove(--top);
                if(c == '(' && ch != ')') return false ;
                if(c == '{' && ch != '}') return false ;
                if(c == '[' && ch != ']') return false ;
            }
        }
        return top==0;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)