不规则二维数组在算法题中的应用

不规则二维数组不是“特殊技巧”，而是贴合现实数据形态的自然选择。比如杨辉三角、稀疏矩阵、树层序遍历、DP状态表等，天然就适合这么干：逐行动态分配长度，按需存储，避免空间浪费，遍历时记得以每行实际长度为界就行。

说白了，不规则二维数组在算法题里压根不是什么炫技的东西，它只是如实反映了数据长得什么样。整齐划一的矩形矩阵固然好看，但现实数据往往没那么听话——杨辉三角、稀疏矩阵、树形结构的层序表示、动态规划中那些状态数量参差不齐的表，才是最自然的存在。

杨辉三角：最典型的不规则数组建模

杨辉三角第 n 行有 n+1 个元素，行长度逐行递增。要是非要用一个规则的二维数组去装它，比如声明一个 int[100][100]，结果一半空间都是闲置的，看着就心疼。而不规则数组就能精准匹配这个形状：

• 先声明 int[][] triangle = new int[n][];，只确定行数，列数先不设。
• 再逐行初始化：triangle[i] = new int[i + 1];，每行长度刚好等于行号加1。
• 填值时只需要判断边界情况：if (j == 0 || j == i) triangle[i][j] = 1;，否则就是 triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];。

你看，代码逻辑本身和规则数组几乎一样，但空间省了一大截，而且每行的“长出”是完全自然发生的。

树的层序遍历结果存储

二叉树按层遍历（BFS）之后，每层节点数是不确定的。满二叉树每层呈指数增长，但实际树可能左倾或右倾，层数分布千差万别。把每层节点存到一个一维数组里，再把所有层数组组合成二维数组——这就是标准的不规则结构：

• 用 List> 是逻辑上最直观的等价结构，但算法题常常要求返回 int[][]，那就得手动转一下。
• 具体做法：先 BFS 一遍统计每层节点数，然后分配每行长度，最后再遍历填值。
• 遍历时千万别默认 result[i].length == result[0].length，内层循环上限必须是 result[i].length，否则下标越界。

这其实很合理：你遍历树的时候，树自己告诉你每层有多少个节点，那就按它说的来分配长度，何必硬塞进一个正方形里？

动态规划中的非对称状态表

有些 DP 问题的状态维度天生就不统一。比如“单词拆分 II”这道题，dp[i] 存储所有能组成前 i 个字符的句子列表，不同 i 对应的句子数量可能差出几个数量级：

• 可以建模为 List dp，再转成 String[][]，本质上就是不规则二维数组。
• 回溯填充的时候，每行长度由实际解的数量决定，你根本没法预设列数，强行固定列只会浪费内存或者丢掉解。
• 输出或进一步处理时，必须逐行判空、逐元素访问，跳过那些可能为 null 的行。

这种场景下，不规则数组不是“优化选项”，而是唯一自然的表达方式——问题本身决定了数据形状不规则，你用规则数组反而要额外处理一堆边界逻辑。

稀疏数据的紧凑表示

当二维数据里大量位置是空的——比如棋盘上只有少数格子有棋子、社交图中只有部分用户有好友关系——用不规则数组替代全量矩阵，节省的空间和时间都很可观：

• 做法是每行只存该行所有非零元素的列索引与值对，形成 int[][] sparseRows。
• 遍历统计时，外层循环行号，内层循环该行实际有效项，完全不用扫描全列，复杂度从 O(行数×列数) 降到 O(非零元素个数)。
• 如果还需要快速列向查询，可以额外维护一个哈希表或二分查找结构，不过那是另一个话题了。

本质上，不规则二维数组的价值就在于“按需分配”和“如实反映结构”。在算法题里，它往往是优化空间复杂度、匹配问题本征形状的关键一步，绝不是为了炫技而用的花架子。