LeetCode 329. 矩阵中的最长递增路径
目录
题目描述
题意分析
输入是一个 $m \times n$ 的整数矩阵，要求返回矩阵中最长严格递增路径所包含的格子数。路径每一步只能走上、下、左、右四个方向，不能斜着走，也不能走出边界。
题面里最值得抠的两个字是「严格」。相邻两格必须满足后一格的值严格大于前一格，相等不算。这条约束顺手带来了一个极强的性质：如果把每个格子看成一个点，从小值格子向相邻的大值格子连一条有向边，那么沿着任何一条边走，格子的值都严格变大。数值只增不减，就永远回不到走过的格子，这张图天然是有向无环的。
这个性质的分量比它看上去要重。它意味着「路径」这个概念在这里不会自我纠缠：从任何一个格子出发，能走出的最长距离是一个确定的、只由矩阵内容决定的量，跟你是从哪里、沿着什么路线走到它的完全无关。
边界上，矩阵至少有一个格子，所以答案至少是 $1$，单个格子本身就是一条长度为 $1$ 的合法路径。另一个极端是整个矩阵所有值都相同，此时任意两个相邻格子都不满足严格递增，答案依然是 $1$。返回值是格子数而不是边数，这一点决定了初值该取 $1$ 而不是 $0$。
解法：DFS 记忆化搜索
核心思路
问题关键：把每个格子看成图节点，只从当前值连向相邻的更大值。沿边数值严格递增，因此不可能形成环；问题就变成了有向无环图上的最长路径。
为什么选 DFS + 记忆化：朴素 DFS 会从不同起点反复计算相同后缀。定义
\[memo[row][col] = 1 + \max memo[nextRow][nextCol]\]memo[row][col]为“从当前格子出发的最长递增路径长度”，则其中下一格必须合法且值更大；若不存在这样的邻格，状态就是 1。每个状态只计算一次，后续直接复用。
不变量与正确性：DFS 返回时，
memo[row][col]已经等于从该格出发的最优长度。所有可走邻格的值都更大，它们的状态会先递归求出；最长合法路径必然选择其中一个邻格继续，取最大值再加当前格即可覆盖所有可能。严格递增保证递归无环，因此不需要visited。最长路径的起点未知，所以要把每个格子都作为起点取最大值。
memo初始为 0，而合法路径最短为 1，因而 0 可以直接表示“尚未计算”。拓扑排序也能做到 $O(mn)$，但记忆化 DFS 更贴合状态定义、代码更直接。
解题步骤
- 创建与矩阵同尺寸的
memo，初值均为 0。- 枚举每个格子作为起点，调用 DFS，并更新全局最大值。
- DFS 命中缓存时直接返回；否则先令当前最优值为 1。
- 枚举四个方向，只对值严格更大的合法邻格递归，使用
dfs(next) + 1更新最优值。- 将最终结果写入
memo[row][col]后返回。对
[[9,9,4],[6,6,8],[2,1,1]]，记忆化会复用9、6等格子的结果，最长链为1 -> 2 -> 6 -> 9，长度为 4。
代码实现
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] memo = new int[m][n];
int ans = 0;
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
ans = Math.max(ans, dfs(matrix, memo, row, col));
}
}
return ans;
}
private int dfs(int[][] matrix, int[][] memo, int row, int col) {
if (memo[row][col] != 0) {
return memo[row][col];
}
int best = 1;
for (int[] dir : DIRS) {
int nextRow = row + dir[0];
int nextCol = col + dir[1];
if (nextRow >= 0 && nextRow < matrix.length
&& nextCol >= 0 && nextCol < matrix[0].length
&& matrix[nextRow][nextCol] > matrix[row][col]) {
best = Math.max(best, dfs(matrix, memo, nextRow, nextCol) + 1);
}
}
memo[row][col] = best;
return best;
}
}
var directions = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func longestIncreasingPath(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
memo := make([][]int, m)
for row := range memo {
memo[row] = make([]int, n)
}
ans := 0
for row := 0; row < m; row++ {
for col := 0; col < n; col++ {
length := dfsIncreasing(matrix, memo, row, col)
if length > ans {
ans = length
}
}
}
return ans
}
func dfsIncreasing(matrix, memo [][]int, row, col int) int {
if memo[row][col] != 0 {
return memo[row][col]
}
best := 1
for _, direction := range directions {
nextRow := row + direction[0]
nextCol := col + direction[1]
if nextRow >= 0 && nextRow < len(matrix) &&
nextCol >= 0 && nextCol < len(matrix[0]) &&
matrix[nextRow][nextCol] > matrix[row][col] {
candidate := dfsIncreasing(matrix, memo, nextRow, nextCol) + 1
if candidate > best {
best = candidate
}
}
}
memo[row][col] = best
return best
}
复杂度分析
- 时间复杂度：$O(mn)$。每个格子的状态只计算一次，每次固定检查四个方向。
- 空间复杂度：$O(mn)$。
memo占 $O(mn)$，递归栈最坏也可能达到 $O(mn)$。
关键点总结
- 严格递增使图天然无环，因此无需
visited。- 状态必须定义为“从当前格子出发”的最长长度，才能跨起点复用。
- 单格路径长度为 1，所以
best初始化为 1，0 可作为缓存哨兵。- 必须枚举所有格子作为起点；无法仅凭局部最小值确定全局起点。
- 若担心极端递归深度，可改用拓扑排序逐层处理，复杂度不变但代码更长。
易错点总结
- 把比较写成
>=：相等格子之间可能互相递归，既违反严格递增，也会形成环。- 额外使用全局
visited：会阻止不同起点复用同一格子的状态；本题的单调性已经保证无环。best初始化为 0：单格矩阵会返回 0，并与“未计算”的缓存哨兵冲突。- 只从左上角或全局最小值搜索：最长路径未必从这些位置开始，会漏解。
- 在枚举完四个方向前写缓存：会缓存尚未完成的局部最优值，后续复用后答案偏小。
- 允许斜向移动：题目只允许上下左右四个方向。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 112. 矩阵中的最长递增路径 | 困难 | 同题换皮，可直接套用同一份记忆化代码 |
| 417. 太平洋大西洋水流问题 | 中等 | 同样靠单调性免除判重，但改为从边界反向灌水 |
| 300. 最长递增子序列 | 中等 | 递增最长链的一维版，状态同为「以此处结尾」 |
| 79. 单词搜索 | 中等 | 反例对照：路径可回头，必须写 visited 并回溯 |
| 576. 出界的路径数 | 中等 | 网格记忆化多一维步数，且求方案数而非最值 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 网格最短路要用 BFS，DFS 记忆化在此不适用 |