求解LeetCode k-th-symbol-in-grammar题出现Java堆内存溢出错误

• 内存溢出的核心原因是你选择了暴力生成完整第n行序列的实现思路：当n=30时，第n行的长度是2^(29) = 536870912个int元素，单个int占4字节，仅这个数组就需要占用约2GB内存，远远超过JVM默认的堆内存上限，自然会抛出OOM错误。
• 额外的无效开销：你采用了递归生成整行的逻辑，过程中没有提前终止的判断，哪怕只需要第k个元素，也要生成完整的整行数组，做了大量无效计算。

该题的核心规律是：第n行的前半段和第n-1行完全相同，后半段是第n-1行每一位取反的结果。我们不需要生成完整数组，只需要递归判断k的位置即可，时间复杂度O(n)，空间占用极低。
优化后的递归实现代码如下：

public class kthGrammer {
    public static int kthGrammar(int n, int k) {
        // 边界条件：第一行只有1个元素0
        if (n == 1) {
            return 0;
        }
        // 第n行的一半长度
        int half = 1 << (n - 2);
        // k在前半段，和n-1行的k位置取值相同
        if (k <= half) {
            return kthGrammar(n - 1, k);
        }
        // k在后半段，是n-1行k-half位置的取值取反
        else {
            return 1 - kthGrammar(n - 1, k - half);
        }
    }

    public static void main(String[] args) {
        System.out.println("\nAnswer: " + kthGrammar(30, 434991989));
    }
}

• 上述实现完全不需要申请大数组，n=30时仅需要30层递归调用，内存占用可以忽略不计，不会出现OOM问题。
• 还可以进一步优化为迭代版本，完全消除递归栈空间占用：

public static int kthGrammar(int n, int k) {
    int res = 0;
    while (n > 1) {
        int half = 1 << (n - 2);
        if (k > half) {
            res = 1 - res;
            k -= half;
        }
        n--;
    }
    return res;
}

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