329. 矩阵中的最长递增路径
题目描述
输入一个 m x n 的整数矩阵 matrix。从任意格子出发，每一步可以走到上、下、左、右相邻的一个格子。不能斜着走，也不能越出矩阵边界，不允许从一边绕到另一边。
如果路径上每一步的下一个格子的值都严格大于当前格子，就称它为递增路径。路径长度按经过的格子数计算。
返回矩阵中最长递增路径的长度。
示例 1
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4
解释：一条最长路径是 1 -> 2 -> 6 -> 9，共 4 个格子。
示例 2
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]] 输出：4
解释：一条最长路径是 3 -> 4 -> 5 -> 6，不能走对角线。
示例 3
输入：matrix = [[1]] 输出：1
解释：只有一个格子，路径长度为 1。
数据范围
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
解题思路：记忆化深度优先搜索
记忆化搜索：dfs(r,c) 表示从 (r,c) 出发的最长递增路径长度，等于 1 加上四个方向中值更大的邻居的 dfs 最大值。由于路径严格递增，不可能成环，所以不需要 visited，每个格子的结果算一次就能存入 memo 复用。答案是所有格子 dfs 的最大值。
为什么正确
memo[r][c] 一旦非 0，就是从 (r,c) 出发的最长递增路径长度的最终值。
复杂度分析
时间 O(mn)，空间 O(mn)（memo 和递归栈）。
易错点
比较必须是严格大于，相等的邻居不能走；不要用 BFS/回溯枚举所有路径，没有 memo 会指数级超时。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
memo = [[0] * n for _ in range(m)]
def dfs(r, c):
if memo[r][c]:
return memo[r][c]
best = 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[r][c] = best
return best
return max(dfs(r, c) for r in range(m) for c in range(n))class Solution {
int m, n;
int[][] memo;
int dfs(int[][] matrix, int r, int c) {
if (memo[r][c] != 0)
return memo[r][c];
int best = 1;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
best = Math.max(best, 1 + dfs(matrix, nr, nc));
}
memo[r][c] = best;
return best;
}
public int longestIncreasingPath(int[][] matrix) {
m = matrix.length; n = matrix[0].length;
memo = new int[m][n];
int ans = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
ans = Math.max(ans, dfs(matrix, r, c));
return ans;
}
}class Solution {
public:
int m, n;
vector<vector<int>> memo;
int dfs(vector<vector<int>>& matrix, int r, int c) {
if (memo[r][c])
return memo[r][c];
int best = 1;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
best = max(best, 1 + dfs(matrix, nr, nc));
}
memo[r][c] = best;
return best;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size(); n = matrix[0].size();
memo.assign(m, vector<int>(n, 0));
int ans = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
ans = max(ans, dfs(matrix, r, c));
return ans;
}
};func longestIncreasingPath(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
memo := make([][]int, m)
for t := range memo {
memo[t] = make([]int, n)
}
var dfs func(r, c int) int
dfs = func(r, c int) int {
if memo[r][c] != 0 {
return memo[r][c]
}
best := 1
for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c] {
best = max(best, 1+dfs(nr, nc))
}
}
memo[r][c] = best
return best
}
ans := 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
ans = max(ans, dfs(r, c))
}
}
return ans
}var longestIncreasingPath = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const memo = Array.from({ length: m }, () => new Array(n).fill(0));
const dfs = (r, c) => {
if (memo[r][c])
return memo[r][c];
let best = 1;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
best = Math.max(best, 1 + dfs(nr, nc));
}
memo[r][c] = best;
return best;
};
let ans = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
ans = Math.max(ans, dfs(r, c));
return ans;
};function longestIncreasingPath(matrix: number[][]): number {
const m = matrix.length, n = matrix[0].length;
const memo: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
const dfs = (r: number, c: number): number => {
if (memo[r][c])
return memo[r][c];
let best = 1;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
best = Math.max(best, 1 + dfs(nr, nc));
}
memo[r][c] = best;
return best;
};
let ans = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
ans = Math.max(ans, dfs(r, c));
return ans;
}其他解法
两种方法都把矩阵看成有向无环图：记忆化搜索从起点向下递归求最长路，拓扑排序从终点一层层剥离并统计层数。
解法 2：拓扑排序（BFS） 时间 O(m·n)，空间 O(m·n)
把每个格子看成节点，从小值指向相邻的大值，得到一张有向无环图。先算出每个格子的出度，即相邻格子中比它大的个数。出度为 0 的格子先入队，逐层出队并把相邻的更小格子出度减 1，减到 0 就进入下一层。层数就是最长递增路径的长度。
没有递归，不会有栈溢出风险。需要额外维护出度数组，代码比记忆化搜索稍长。
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
outdeg = [[0] * n for _ in range(m)]
for r in range(m):
for c in range(n):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
outdeg[r][c] += 1
queue = [(r, c) for r in range(m) for c in range(n) if outdeg[r][c] == 0]
layers = 0
while queue:
layers += 1
nxt = []
for r, c in queue:
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] < matrix[r][c]:
outdeg[nr][nc] -= 1
if outdeg[nr][nc] == 0:
nxt.append((nr, nc))
queue = nxt
return layersclass Solution {
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int[][] outdeg = new int[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
outdeg[r][c]++;
}
List<int[]> queue = new ArrayList<>();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (outdeg[r][c] == 0) queue.add(new int[]{r, c});
int layers = 0;
while (!queue.isEmpty()) {
layers++;
List<int[]> nxt = new ArrayList<>();
for (int[] cell : queue) {
int r = cell[0], c = cell[1];
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] < matrix[r][c]) {
if (--outdeg[nr][nc] == 0) nxt.add(new int[]{nr, nc});
}
}
}
queue = nxt;
}
return layers;
}
}class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<vector<int>> outdeg(m, vector<int>(n, 0));
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
outdeg[r][c]++;
}
vector<pair<int, int>> queue;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (outdeg[r][c] == 0) queue.push_back({r, c});
int layers = 0;
while (!queue.empty()) {
layers++;
vector<pair<int, int>> nxt;
for (auto [r, c] : queue) {
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] < matrix[r][c]) {
if (--outdeg[nr][nc] == 0) nxt.push_back({nr, nc});
}
}
}
queue = nxt;
}
return layers;
}
};func longestIncreasingPath(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
outdeg := make([][]int, m)
for r := range outdeg {
outdeg[r] = make([]int, n)
}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c] {
outdeg[r][c]++
}
}
}
}
queue := [][2]int{}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if outdeg[r][c] == 0 {
queue = append(queue, [2]int{r, c})
}
}
}
layers := 0
for len(queue) > 0 {
layers++
nxt := [][2]int{}
for _, cell := range queue {
r, c := cell[0], cell[1]
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] < matrix[r][c] {
outdeg[nr][nc]--
if outdeg[nr][nc] == 0 {
nxt = append(nxt, [2]int{nr, nc})
}
}
}
}
queue = nxt
}
return layers
}var longestIncreasingPath = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const outdeg = Array.from({ length: m }, () => new Array(n).fill(0));
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
outdeg[r][c]++;
}
let queue = [];
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (outdeg[r][c] === 0) queue.push([r, c]);
let layers = 0;
while (queue.length > 0) {
layers++;
const nxt = [];
for (const [r, c] of queue) {
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] < matrix[r][c]) {
if (--outdeg[nr][nc] === 0) nxt.push([nr, nc]);
}
}
}
queue = nxt;
}
return layers;
};function longestIncreasingPath(matrix: number[][]): number {
const m = matrix.length, n = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const outdeg: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
outdeg[r][c]++;
}
let queue: number[][] = [];
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (outdeg[r][c] === 0) queue.push([r, c]);
let layers = 0;
while (queue.length > 0) {
layers++;
const nxt: number[][] = [];
for (const [r, c] of queue) {
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] < matrix[r][c]) {
if (--outdeg[nr][nc] === 0) nxt.push([nr, nc]);
}
}
}
queue = nxt;
}
return layers;
}