Java括号匹配代码功能正常但运行超时无法通过，求性能优化方案

性能瓶颈原因 #

• Stack.add(0, c)操作时间复杂度过高。Java的Stack底层基于Vector实现，在头部插入元素需要将所有已有元素后移一位，单次插入时间复杂度是O(n)，循环插入N个元素总时间复杂度达到O(N²)，数据量大的时候运行速度会大幅下降。
• 存在冗余的数据结构和遍历操作。标准括号匹配问题仅需要1个栈做1次正序遍历即可完成，你额外多初始化了1个栈，还多做了1次全量输入的倒序转存操作，带来了很多不必要的性能开销。
• java.util.Stack本身存在同步开销。Stack是线程安全类，所有方法都带synchronized修饰，单线程判题场景下不需要同步逻辑，额外的锁操作会拖慢运行速度。

优化方案 #

直接使用单个ArrayDeque做正序遍历即可，时间复杂度降到O(N)，空间复杂度保持最坏O(N)，性能可以满足绝大多数判题场景的要求。
优化后代码如下：

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Dyck {
    public boolean checkParentheses(ArrayList<Character> input) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (char c : input) {
            // 左括号直接入栈
            if (c == '(' || c == '[') {
                stack.push(c);
                continue;
            }
            // 遇到右括号时栈为空，直接返回不匹配
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            // 括号类型不匹配直接返回false
            if ((c == ')' && top != '(') || (c == ']' && top != '[')) {
                return false;
            }
        }
        // 遍历完所有字符后栈为空才完全匹配
        return stack.isEmpty();
    }
}

如果需要进一步压榨性能，可以将增强for循环替换为普通下标for循环遍历ArrayList，减少迭代器的额外开销。

内容的提问来源于stack exchange，提问作者Fakutzki