本文详解为何原递归解法因无方向约束导致栈溢出，并提供基于四向预处理的 o(n²) 动态规划替代方案，兼顾正确性、效率与可读性。
本文详解为何原递归解法因无方向约束导致栈溢出，并提供基于四向预处理的 o(n²) 动态规划替代方案，兼顾正确性、效率与可读性。
在 leetcode 第 764 题「最大加号标志」中，目标是找出以某点为中心、四个方向（上、下、左、右）连续非矿格延伸长度的最小值（即“臂长”），再取所有中心点对应臂长的最大值。初学者常尝试用记忆化递归（如 @cache 装饰的 helper(r, c)）模拟“向四周扩散”，但该思路存在根本性缺陷：递归未建模方向性，导致无限循环调用。
例如，helper(1,1) 可能调用 helper(1,2)，而后者又调用 helper(1,1)（通过 c-1 回退），形成 (1,1) ↔ (1,2) 的死循环。即使添加了边界和矿点判断作为“伪终止条件”，也无法阻止这种无向回溯——因为 helper 的语义是“从 (r,c) 出发能延伸多远”，而非“沿某一固定方向能延伸多远”。缓存（@cache）在此场景下不仅无法剪枝，反而掩盖了逻辑错误，使栈深度持续累积直至 RecursionError。
✅ 正确解法应剥离方向耦合，采用四向独立预处理 + 常数时间查询策略：
- 定义四个二维数组：top[i][j] 表示从 (i,j) 向上连续非矿格数量（含自身）；
- 类似定义 bot[i][j]（向下）、left[i][j]（向左）、right[i][j]（向右）；
- 每个数组可在单次遍历中线性构建（利用前缀思想：遇到矿则重置为 0，否则 +1）；
- 最终对每个 (i,j)，其最大加号阶数为 min(top[i][j], bot[i][j], left[i][j], right[i][j])。
以下是完整、高效且易理解的实现：
class Solution: def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int: # 将 mines 转为 set 便于 O(1) 查询 mine_set = {tuple(mine) for mine in mines} R = range(n) # 初始化四向 DP 数组 top = [[0] * n for _ in R] bot = [[0] * n for _ in R] left = [[0] * n for _ in R] right = [[0] * n for _ in R] # 第一遍：计算 top（自上而下）和 left（自左而右） for i in R: s_top = s_left = 0 for j in R: # top[i][j]: 从第0行到第i行，(i,j)向上连续非矿数 if (i, j) in mine_set: s_top = 0 else: s_top += 1 top[i][j] = s_top # left[i][j]: 从第0列到第j列，(i,j)向左连续非矿数 if (j, i) in mine_set: # 注意：此处利用对称索引更新 left[j][i] s_left = 0 else: s_left += 1 left[j][i] = s_left # 第二遍：计算 bot（自下而上）和 right（自右而左） for i in R: s_bot = s_right = 0 for j in reversed(R): # bot[i][j]: 从第n-1行到第i行，(i,j)向下连续非矿数 if (i, j) in mine_set: s_bot = 0 else: s_bot += 1 bot[i][j] = s_bot # right[i][j]: 从第n-1列到第j列，(i,j)向右连续非矿数 if (j, i) in mine_set: s_right = 0 else: s_right += 1 right[j][i] = s_right # 枚举每个中心点，取四向最小值的最大值 ans = 0 for i in R: for j in R: arm = min(top[i][j], bot[i][j], left[i][j], right[i][j]) ans = max(ans, arm) return ans⚠️ 关键注意事项：
- 索引对称技巧（如用 (j,i) 更新 left[j][i]）是为了复用同一循环结构，避免写四遍相似代码；若追求极致清晰，可拆分为四个独立双层循环；
- 所有 DP 数组初始化为 0，矿点处值恒为 0，天然满足“中断即归零”的要求；
- 时间复杂度严格为 O(n²)，空间复杂度 O(n²)，远优于错误递归解法的指数级潜在调用栈；
- 本方法具备良好扩展性，类似“最长连续序列”“直方图最大矩形”等问题均可借鉴此类“方向解耦 + 前缀DP”范式。
总结：递归不是万能钥匙。当问题本质具有强方向性或局部依赖时，优先考虑迭代式动态规划——它更可控、更高效，也更贴近计算机的实际执行逻辑。