LeetCode中orderOfLargestPlusSign函数递归深度超出问题求助

问题根源 #

• 递归循环依赖：你的helper(r,c)函数会调用上下左右四个相邻单元格的helper，比如helper(r,c)调用helper(r+1,c)，而helper(r+1,c)又会反过来调用helper(r,c)。第一次触发这种互相调用时，两个函数都还没被@cache缓存，会形成无限递归链，直接导致栈溢出。
• 基准条件无法终止循环：只有越界或碰到地雷时才返回0，但正常相邻单元格不会触发这个条件，递归会一直持续下去。

正确解法：动态规划迭代实现 #

递归思路在这里天然存在循环依赖问题，改用动态规划迭代计算每个单元格四个方向的连续有效长度是更合理的方案：

from typing import List

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        mine_set = set(tuple(mine) for mine in mines)
        # 初始化四个方向的连续长度数组
        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)]
        
        # 计算向上的连续有效长度（从上到下遍历）
        for r in range(n):
            for c in range(n):
                if (r, c) not in mine_set:
                    up[r][c] = up[r-1][c] + 1 if r > 0 else 1
        
        # 计算向下的连续有效长度（从下到上遍历）
        for r in range(n-1, -1, -1):
            for c in range(n):
                if (r, c) not in mine_set:
                    down[r][c] = down[r+1][c] + 1 if r < n-1 else 1
        
        # 计算向左的连续有效长度（从左到右遍历）
        for c in range(n):
            for r in range(n):
                if (r, c) not in mine_set:
                    left[r][c] = left[r][c-1] + 1 if c > 0 else 1
        
        # 计算向右的连续有效长度（从右到左遍历）
        for c in range(n-1, -1, -1):
            for r in range(n):
                if (r, c) not in mine_set:
                    right[r][c] = right[r][c+1] + 1 if c < n-1 else 1
        
        max_order = 0
        # 遍历每个单元格，取四个方向的最小值作为当前加号阶数
        for r in range(n):
            for c in range(n):
                if (r, c) not in mine_set:
                    current = min(up[r][c], down[r][c], left[r][c], right[r][c])
                    max_order = max(max_order, current)
        return max_order

逻辑说明 #

1. 分别计算每个单元格上、下、左、右四个方向的连续有效（非地雷）长度，用迭代方式避免递归循环。
2. 每个单元格的加号阶数等于四个方向长度的最小值，遍历所有单元格取最大值即可。

内容的提问来源于stack exchange，提问作者Ruchika Gupta