LeetCode: 2684. 矩阵中移动的最大次数

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

2684. 矩阵中移动的最大次数

LeetCode - 2684. 矩阵中移动的最大次数

给你一个下标从 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 <= 10⁵
1 <= grid[i][j] <= 10⁶

思路分析

首先想到的思路是回溯，从第一列每个位置出发，向右进行探索，成功前进，失败则回溯。思路正确，通过 810 / 814 个测试用例。然后，超时。

又想了想，这不能叫回溯，因为没有回溯动作。应该是深度优先搜索。

后想到动态规划。初始化一个同样大小的二维数组，每个表格记录到达该点需要行走记录。从左向右，按列遍历即可。

一刷（深度优先搜索）
一刷（动态规划）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 通过 810 / 814 个测试用例。超时
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-05-05 22:11:52
 */
public int maxMoves(int[][] grid) {
  int result = 0;
  for (int i = 0; i < grid.length; i++) {
    result = Math.max(result, dfs(grid, i, 0));
    if (result == grid[i].length) {
      break;
    }
  }
  return result;
}

private int dfs(int[][] grid, int row, int column) {
  if (column == grid[row].length - 1) {
    return 0;
  }
  int result = -1;
  if (row - 1 >= 0 && column + 1 < grid[row - 1].length
    && grid[row][column] < grid[row - 1][column + 1]) {
    result = Math.max(result, dfs(grid, row - 1, column + 1));
  }
  if (column + 1 < grid[row].length
    && grid[row][column] < grid[row][column + 1]) {
    result = Math.max(result, dfs(grid, row, column + 1));
  }
  if (row + 1 < grid.length && column + 1 < grid[row + 1].length
    && grid[row][column] < grid[row + 1][column + 1]) {
    result = Math.max(result, dfs(grid, row + 1, column + 1));
  }
  // 受灵茶山艾府题解启发，加这么一行代码，答案即可通过。
  grid[row][column] = 0;
  return result + 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-05-05 22:38:45
 */
public int maxMoves(int[][] grid) {
  int m = grid.length, n = grid[0].length;
  int[][] dp = new int[m][n];
  int result = 0;
  // 📢：注意这里的遍历顺序，需要按列向右推进
  for (int column = 1; column < n; column++) {
    // 不加 stop，击败 12.96%；加 stop，击败 50.07%
    boolean stop = true;
    for (int row = 0; row < m; row++) {
      if (row - 1 >= 0 && grid[row - 1][column - 1] < grid[row][column]
        && (column == 1 || dp[row - 1][column - 1] > 0)) {
        dp[row][column] = Math.max(dp[row][column], dp[row - 1][column - 1] + 1);
        stop = false;
      }
      if (grid[row][column - 1] < grid[row][column]
        && (column == 1 || dp[row][column - 1] > 0)) {
        dp[row][column] = Math.max(dp[row][column], dp[row][column - 1] + 1);
        stop = false;
      }
      if (row + 1 < m && grid[row + 1][column - 1] < grid[row][column]
        && (column == 1 || dp[row + 1][column - 1] > 0)) {
        dp[row][column] = Math.max(dp[row][column], dp[row + 1][column - 1] + 1);
        stop = false;
      }
      result = Math.max(result, dp[row][column]);
    }
    if (stop) {
      return result;
    }
  }
  return result;
}

参考资料

2684. 矩阵中移动的最大次数 - 官方题解 — 广度优先搜索的解法。其实，每次遍历只需要保存当前列可以到达的节点坐标即可，当没有坐标可以到达时，已经走到了尽头。这个解法更简单高效。
2684. 矩阵中移动的最大次数 - 两种方法：DFS / BFS — 深度优先遍历的解法非常有意思，把到达的处理后的节点都设置成 0，这样就可以有效避免重复遍历，加快处理速度。