LeetCode 题解工作台
矩阵中的最长递增路径
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外 （即不允许环绕）。 示例 1： 输入： matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出…
8
题型
5
代码语言
3
相关题
当前训练重点
困难 · 动态·规划
答案摘要
我们设计一个函数 $dfs(i, j)$，它表示从矩阵中的坐标 $(i, j)$ 出发，可以得到的最长递增路径的长度。那么答案就是 $\max_{i, j} \textit{dfs}(i, j)$。 函数 $dfs(i, j)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]] 输出：1
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
解题思路
方法一：记忆化搜索
我们设计一个函数 ，它表示从矩阵中的坐标 出发，可以得到的最长递增路径的长度。那么答案就是 。
函数 的执行逻辑如下：
- 如果 已经被访问过，直接返回 ；
- 否则对 进行搜索，搜索四个方向的坐标 ，如果满足 以及 ，那么对 进行搜索。搜索结束后，将 更新为 。最后返回 。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
相似题目：
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
@cache
def dfs(i: int, j: int) -> int:
ans = 0
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
ans = max(ans, dfs(x, y))
return ans + 1
m, n = len(matrix), len(matrix[0])
return max(dfs(i, j) for i in range(m) for j in range(n))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should understand how to efficiently traverse the matrix using graph-like techniques such as topological sort.
- question_mark
Look for a clear explanation of how DFS with memoization avoids recalculating paths.
- question_mark
Expect discussion on how to handle large input sizes and edge cases such as matrices with only one cell or uniform values.
常见陷阱
外企场景- error
Ignoring boundary conditions and invalid moves (e.g., out-of-bound or non-increasing paths).
- error
Failing to optimize with memoization, leading to redundant DFS calls and time inefficiency.
- error
Overcomplicating the problem by using unnecessary algorithms instead of focusing on graph-based approaches.
进阶变体
外企场景- arrow_right_alt
Handling a matrix with only one cell.
- arrow_right_alt
Optimizing for larger matrix sizes by reducing the overhead of DFS or BFS.
- arrow_right_alt
Implementing the solution without using memoization or dynamic programming techniques.