矩阵中移动的最大次数
难度:
标签:
题目描述
You are given a 0-indexed m x n matrix grid consisting of positive integers.
You can start at any cell in the first column of the matrix, and traverse the grid in the following way:
- From a cell
(row, col), you can move to any of the cells:(row - 1, col + 1),(row, col + 1)and(row + 1, col + 1)such that the value of the cell you move to, should be strictly bigger than the value of the current cell.
Return the maximum number of moves that you can perform.
Example 1:
Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]] Output: 3 Explanation: We can start at the cell (0, 0) and make the following moves: - (0, 0) -> (0, 1). - (0, 1) -> (1, 2). - (1, 2) -> (2, 3). It can be shown that it is the maximum number of moves that can be made.
Example 2:
Input: grid = [[3,2,4],[2,1,9],[1,1,7]] Output: 0 Explanation: Starting from any cell in the first column we cannot perform any moves.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1051 <= grid[i][j] <= 106
代码结果
运行时间: 68 ms, 内存: 24.7 MB
/*
* Problem: Similar to the Java solution, this uses Java Streams to solve the problem.
* Approach: Utilize IntStream to traverse and filter through the possible moves.
*/
import java.util.stream.IntStream;
public class MaxMovesInGridStream {
public int maxMoves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int col = n - 2; col >= 0; col--) {
for (int row = 0; row < m; row++) {
int currentValue = grid[row][col];
dp[row][col] = IntStream.of(
(row > 0 && grid[row - 1][col + 1] > currentValue ? dp[row - 1][col + 1] + 1 : 0),
(grid[row][col + 1] > currentValue ? dp[row][col + 1] + 1 : 0),
(row < m - 1 && grid[row + 1][col + 1] > currentValue ? dp[row + 1][col + 1] + 1 : 0)
).max().orElse(0);
}
}
return IntStream.range(0, m).map(row -> dp[row][0]).max().orElse(0);
}
}
解释
方法:
此题解采用深度优先搜索（DFS）方法来遍历矩阵中可能的路径。对于矩阵中的每个单元格，可以向右上（row - 1, col + 1）、正右（row, col + 1）和右下（row + 1, col + 1）移动，但前提是目标单元格的值必须严格大于当前单元格的值。从第一列的每一个单元格开始，尝试所有可能的路径，并使用一个全局变量 `ans` 来跟踪到达的最远列号。最终，返回的最大移动次数是 `ans`。题解中还利用了一个技巧：将已访问的单元格置为0（因为矩阵元素为正整数），这防止了重复访问并可能优化了DFS性能。
时间复杂度:
O(3^(m*n))
空间复杂度:
O(min(m, n))
代码细节讲解
🦆
在DFS中，将已访问的单元格值置为0的做法是否会影响其他可能的路径遍历？
▷🦆
递归实现的DFS在处理大矩阵时可能会导致栈溢出，有没有其他更适合处理大数据集的方法？
▷🦆
题解中提到最大递归深度可以达到min(m, n)，这是否考虑了所有可能的路径情况，例如可能的对角线或蛇形路径？
▷🦆
题解提到如果DFS已达到最右列就提前返回，这种提前返回的策略是否可能错过其他更长的路径？
▷