LeetCode中的最大加号标志题目要求在一个由0和1组成的矩阵中，找到最大的加号标志的阶数。加号标志的阶数定义为从中心向四个方向延伸的连续1的长度的最小值，很多开发者一开始会尝试用递归的方式计算每个位置四个方向的连续1长度，但这种做法很容易触发递归深度超限的错误。
问题出现的原因
递归思路通常是针对每个位置，分别向上下左右四个方向递归统计连续1的长度，再取最小值作为该位置的加号阶数。但当矩阵规模较大时，比如矩阵边长达到500，每个位置的递归调用层级会不断叠加，最终超过Python等语言默认的递归栈深度（通常是1000），就会抛出递归深度超限的异常。
解决方案一：动态规划自底向上计算
动态规划可以完全避免递归调用，通过四次遍历矩阵，分别记录每个位置向上、下、左、右四个方向的连续1长度，最后取四个方向的最小值作为该位置的加号阶数，再全局取最大值即可。
具体实现步骤如下：
- 初始化四个二维数组，分别记录每个位置四个方向的连续1长度，初始值都为0
- 第一次遍历：从上到下计算每个位置向上的连续1长度，如果当前位置是1，长度等于上方位置长度加1，否则为0
- 第二次遍历：从下到上计算每个位置向下的连续1长度，规则同上
- 第三次遍历：从左到右计算每个位置向左的连续1长度，规则同上
- 第四次遍历：从右到左计算每个位置向右的连续1长度，规则同上
- 遍历所有位置，取四个方向长度的最小值作为该位置的加号阶数，记录全局最大值
对应的代码实现如下：
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
# 初始化矩阵，1表示可放置加号，0表示不可放置
grid = [[1] * n for _ in range(n)]
for x, y in mines:
grid[x][y] = 0
# 初始化四个方向的连续1长度数组
up = [[0] * n for _ in range(n)]
down = [[0] * n for _ in range(n)]
left = [[0] * n for _ in range(n)]
right = [[0] * n for _ in range(n)]
# 计算向上的连续1长度
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
up[i][j] = 1
if i > 0:
up[i][j] = up[i-1][j] + 1
# 计算向下的连续1长度
for i in range(n-1, -1, -1):
for j in range(n):
if grid[i][j] == 1:
down[i][j] = 1
if i < n-1:
down[i][j] = down[i+1][j] + 1
# 计算向左的连续1长度
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
left[i][j] = 1
if j > 0:
left[i][j] = left[i][j-1] + 1
# 计算向右的连续1长度
for i in range(n):
for j in range(n-1, -1, -1):
if grid[i][j] == 1:
right[i][j] = 1
if j < n-1:
right[i][j] = right[i][j+1] + 1
# 计算最大加号阶数
max_order = 0
for i in range(n):
for j in range(n):
current = min(up[i][j], down[i][j], left[i][j], right[i][j])
if current > max_order:
max_order = current
return max_order
解决方案二：记忆化递归优化
如果一定要使用递归思路，可以通过记忆化缓存每个位置四个方向的计算结果，避免重复递归调用，减少递归层级。但这种方法仍然有递归栈的限制，只适合矩阵规模较小的情况。
实现时需要用一个缓存字典存储已经计算过的位置和方向的结果，每次递归前先检查缓存，如果已经计算过就直接返回，避免重复调用。
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
grid = [[1] * n for _ in range(n)]
for x, y in mines:
grid[x][y] = 0
# 缓存字典，key为(i,j,dir)，dir表示方向：0上1下2左3右
cache = {}
def dfs(i, j, dir):
# 越界或者当前位置是0，返回0
if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] == 0:
return 0
# 如果缓存中有结果，直接返回
if (i, j, dir) in cache:
return cache[(i, j, dir)]
# 根据方向递归计算
if dir == 0:
res = 1 + dfs(i-1, j, dir)
elif dir == 1:
res = 1 + dfs(i+1, j, dir)
elif dir == 2:
res = 1 + dfs(i, j-1, dir)
else:
res = 1 + dfs(i, j+1, dir)
cache[(i, j, dir)] = res
return res
max_order = 0
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
up_len = dfs(i, j, 0)
down_len = dfs(i, j, 1)
left_len = dfs(i, j, 2)
right_len = dfs(i, j, 3)
current = min(up_len, down_len, left_len, right_len)
if current > max_order:
max_order = current
return max_order
方案对比
两种方案的适用场景不同，具体对比如下：
| 方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 动态规划 | 无递归深度限制，时间复杂度稳定，执行效率高 | 需要额外空间存储四个方向的数组 | 所有规模的矩阵，尤其是大矩阵 |
| 记忆化递归 | 思路符合直觉，代码逻辑简单 | 仍有递归栈限制，大规模矩阵容易超限 | 小规模矩阵，或者递归深度可控的场景 |
总结
解决最大加号标志的递归深度超限问题，最优的选择是改用动态规划的实现方式，从根源上避免递归调用带来的栈深度限制。如果坚持使用递归，一定要加上记忆化缓存，同时评估矩阵规模是否在递归栈允许的范围内。在实际刷题时，遇到类似需要多方向统计连续元素的问题，优先选择动态规划往往能避免很多边界问题。