矩阵中移动的最大次数

标签: 数组 动态规划 矩阵

难度: Medium

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

  • 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：


输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 105
  • 1 <= grid[i][j] <= 106

Submission

运行时间: 68 ms

内存: 24.7 MB

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        def dfs(i: int, j: int) -> None:
            nonlocal ans
            ans = max(ans, j)
            if ans == n - 1:  # ans 已达到最大值
                return
            for k in i - 1, i, i + 1:  # 向右上/右/右下走一步
                if 0 <= k < m and grid[k][j + 1] > grid[i][j]:
                    dfs(k, j + 1)
            grid[i][j] = 0
        for i in range(m):
            dfs(i, 0)  # 从第一列的任一单元格出发
        return ans

Explain

此题解采用深度优先搜索（DFS）方法来遍历矩阵中可能的路径。对于矩阵中的每个单元格，可以向右上（row - 1, col + 1）、正右（row, col + 1）和右下（row + 1, col + 1）移动，但前提是目标单元格的值必须严格大于当前单元格的值。从第一列的每一个单元格开始，尝试所有可能的路径，并使用一个全局变量 `ans` 来跟踪到达的最远列号。最终，返回的最大移动次数是 `ans`。题解中还利用了一个技巧：将已访问的单元格置为0（因为矩阵元素为正整数），这防止了重复访问并可能优化了DFS性能。

时间复杂度: O(3^(m*n))

空间复杂度: O(min(m, n))

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])  # 获取矩阵的行数和列数
        ans = 0  # 初始化最大移动次数的变量
        def dfs(i: int, j: int) -> None:  # 定义DFS函数
            nonlocal ans  # 引用外部变量ans
            ans = max(ans, j)  # 更新到达的最远列号
            if ans == n - 1:  # 如果已达到最右列，提前返回
                return
            for k in i - 1, i, i + 1:  # 遍历三个可能的移动方向
                if 0 <= k < m and grid[k][j + 1] > grid[i][j]:  # 检查移动是否合法
                    dfs(k, j + 1)  # 递归进行DFS搜索
            grid[i][j] = 0  # 访问过的单元格标记为0防止重复访问
        for i in range(m):  # 从每一个第一列的单元格开始DFS搜索
            dfs(i, 0)  # 开始DFS
        return ans  # 返回最大移动次数

Explore

是的，这种做法确实会影响其他可能的路径遍历。通过将单元格值置为0来标记已访问，这防止了从其他起始点通过该单元格的潜在路径，因为后续的DFS遍历将不会考虑值为0的单元格。这可能会阻止探索从不同起点出发可能达到更远列的路径，因此这种方法可能不会探索所有合法的路径。

确实，递归实现的DFS在处理大矩阵时可能会导致栈溢出，特别是当递归深度非常大时。作为替代，可以使用迭代的深度优先搜索（使用显式栈）或广度优先搜索（BFS）来避免大递归深度的问题。BFS使用队列来实现，可以有效地处理更大的数据集，尤其是在需要广泛搜索每层节点时。此外，迭代版本的DFS和BFS通常更容易控制内存使用，适合大规模数据处理。

题解中提到的最大递归深度考虑了从矩阵一边到另一边的最直接路径，但并没有完全考虑所有可能的复杂路径，如对角线或蜿蜒前进的路径。在实际的DFS实现中，路径的选择可能会更加复杂和多变，特别是在矩阵元素允许多种移动方向的情况下。因此，实际的递归深度可能会超过min(m, n)，尤其是在路径需要多次转向以避开不能移动的单元格时。

题解中提到的提前返回策略基于到达最右列的观察，其假设是一旦到达最右列，就已经找到了一条可行的路径，因此不需要继续探索。然而，这种策略确实有可能错过其他起点出发的更长或更优的路径，特别是在存在多条路径可以到达最右列但长度不同的情况下。这种策略优化了搜索效率，但可能牺牲了解的全面性。