LeetCode 20题有效括号代码本地与平台结果不一致排查

我针对LeetCode第20题《有效括号》写了一份对数空间复杂度的代码，题目要求验证三种括号是否按顺序成对闭合。本地输入"()[]{}"返回true，但在LeetCode平台测试返回false，求帮忙运行并排查问题原因。

class Solution18_1 {
    private Map<Character, Character> otherSide = new HashMap<>();
    private int t1l = -1, t2l = -1, t3l = -1, t1r = Integer.MAX_VALUE, t2r = Integer.MAX_VALUE, t3r = Integer.MAX_VALUE;

    private void initializeMap() {
        otherSide.put('{', '}');
        otherSide.put('(', ')');
        otherSide.put('[', ']');
    }

    public boolean isValid(String s) {
        initializeMap();
        //step one, check if all three types match on numbers,
        // a { must have a }, so for the other two types
        int matchCounter = 0;
        matchCounter = matchCheck('{', s);
        if (matchCounter != 0) return false;
        matchCounter = matchCheck('[', s);
        if (matchCounter != 0) return false;
        matchCounter = matchCheck('(', s);
        if (matchCounter != 0) return false;

        //step two, check if order matches
        //When we firstly read a type, we start to find the indices of this pair
        //if the next read type is the same as the last one, we update the pointers.
        //if the next read type is not the same type, we find the pair and compare the orders
        char lastType = 0;
        for (int i = 0; i < s.length(); i++) {
//            System.out.println("dealing with index " + i + ",the current char is " + s.charAt(i) + ", and matchCount = " + matchCounter
//                    + ", last type is " + lastType);
            if (lastType == 0) {
                lastType = s.charAt(i);
                matchCounter = 1;
                if (lastType == '{') t1l = i;
                if (lastType == '[') t2l = i;
                if (lastType == '(') t3l = i;
            } else if (matchCounter != 0 && s.charAt(i) == lastType) {
                matchCounter++;
            } else if (matchCounter != 0 && s.charAt(i) == otherSide.get(lastType)) {
                matchCounter--;
                if (matchCounter == 0) {
                    //pairs located, check if matches
                    //and go back to the corresponding index
//                    System.out.print("Going back, ");
                    if (lastType == '{') {
//                        System.out.println("we read {, hence use t1l : " + t1l);
                        t1r = i;
                        i = t1l;
                        if (!checkMatch(1)) return false;
                    }
                    if (lastType == '[') {
//                        System.out.println("we read [, hence use t2l : " + t2l);
                        t2r = i;
                        i = t2l;
                        if (!checkMatch(2)) return false;
                    }
                    if (lastType == '(') {
//                        System.out.println("we read (, hence use t3l : " + t3l);
                        t3r = i;
                        i = t3l;
                        if (!checkMatch(3)) return false;
                    }
                }
            } else if (matchCounter == 0 && s.charAt(i) == lastType) {
                matchCounter = 1;
                if (lastType == '{') t1l = i;
                if (lastType == '[') t2l = i;
                if (lastType == '(') t3l = i;
            } else if (matchCounter == 0 && (s.charAt(i) != lastType && s.charAt(i) != otherSide.get(lastType))) {
//                System.out.println("\nChanging lastType by " + s.charAt(i));
                matchCounter = 1;
                lastType = s.charAt(i);
                if (lastType == '{') t1l = i;
                if (lastType == '[') t2l = i;
                if (lastType == '(') t3l = i;
            }


        }

        return true;
    }

    private boolean checkMatch(int i) {
        if (i == 1) {
            if (t1l < t2l && t1r > t2r) {
                if (t1r < t2r) return false;
            } else if (t1l > t2l && t1l < t2r) {
                if (t1r > t2r) return false;
            }

            if (t1l < t3l && t1r > t3r) {
                if (t1r < t3r) return false;
            } else if (t1l > t3l && t1l < t3r) {
                if (t1r > t3r) return false;
            }
        } else if (i == 2) {
            if (t2l < t1l && t2r > t1r) {
                if (t2r < t1r) return false;
            } else if (t2l > t1l && t2l < t1r) {
                if (t2r > t1r) return false;
            }

            if (t2l < t3l && t2r > t3r) {
                if (t2r < t3r) return false;
            } else if (t2l > t3l && t2l < t1r) {
                if (t2r > t3r) return false;
            }

        } else if (i == 3) {
            if (t3l < t1l && t3r > t1r) {
                if (t3r < t1r) return false;
            } else if (t3l > t1l && t3l < t1r) {
                if (t3r > t1r) return false;
            }

            if (t3l < t2l && t3r > t2r) {
                if (t3r < t2r) return false;
            } else if (t3l > t2l && t3l < t2r) {
                if (t3r > t2r) return false;
            }
        }
        return true;
    }

    private int matchCheck(char key, String s) {
        int matchCounter = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == key) {
                matchCounter++;
            } else if (s.charAt(i) == otherSide.get(key)) {
                matchCounter--;
                if (matchCounter < 0) return -1;
            }
        }
        return matchCounter;
    }
}

问题排查结果 #

1. 类名不符合平台要求 #

LeetCode要求提交的类必须严格命名为Solution，你的类名是Solution18_1，平台无法识别入口方法isValid，这是导致测试失败的直接原因之一。

2. 类成员变量未重置 #

t1l、t2l、t1r等是类级别的成员变量，LeetCode会复用同一个类实例处理多个测试用例。前一个测试用例的变量值会残留到下一次测试，导致逻辑判断错误。比如测试完"()[]{}"后，t3r会被设置为1，下一次测试时这个值没有重置，会干扰后续判断。

3. checkMatch方法笔误 #

在i==2（处理[]类型）的分支中，有一行错误代码：

else if (t2l > t3l && t2l < t1r)

这里应该是t2l < t3r，属于笔误，会导致嵌套括号的顺序判断错误。

4. 循环索引回退逻辑错误 #

当匹配完一对括号后，你执行i = t1l（对应类型的左括号索引），这会让循环重新处理已经检查过的字符，引发重复判断甚至死循环。比如输入"()[]{}"时，处理完第一个()后，i回退到0，会重新进入lastType == 0的分支，导致状态混乱。

修复后的代码示例 #

以下是符合平台要求、逻辑正确的代码，同时保持对数空间复杂度（用数组模拟栈，空间复杂度O(n)，如果要严格对数空间可以用递归二分法，但栈实现更简洁高效）：

import java.util.HashMap;
import java.util.Map;

class Solution {
    private final Map<Character, Character> otherSide = new HashMap<>();

    public Solution() {
        otherSide.put('{', '}');
        otherSide.put('(', ')');
        otherSide.put('[', ']');
    }

    public boolean isValid(String s) {
        // 检查每种括号数量是否匹配
        if (matchCheck('{', s) != 0) return false;
        if (matchCheck('[', s) != 0) return false;
        if (matchCheck('(', s) != 0) return false;

        // 用栈验证括号顺序
        int[] stack = new int[s.length()];
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (otherSide.containsKey(c)) {
                // 左括号入栈
                stack[++top] = i;
            } else {
                // 右括号匹配栈顶左括号
                if (top == -1) return false;
                char leftChar = s.charAt(stack[top--]);
                if (otherSide.get(leftChar) != c) return false;
            }
        }
        return top == -1;
    }

    private int matchCheck(char key, String s) {
        int matchCounter = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == key) {
                matchCounter++;
            } else if (s.charAt(i) == otherSide.get(key)) {
                matchCounter--;
                if (matchCounter < 0) return -1;
            }
        }
        return matchCounter;
    }
}

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