LeetCode LCR 112. 矩阵中的最长递增路径

Categories:

题目描述
思路分析
1. 解法一：DFS + 记忆化搜索（推荐）
相似题目

题目描述

✅ LCR 112. 矩阵中的最长递增路径

思路分析

解法一：DFS + 记忆化搜索（推荐）

核心思路：

对每个单元格作为起点进行 DFS，寻找最长递增路径。

用 memo[i][j] 记录从该位置出发的最长长度，避免重复计算。

四个方向扩展，满足严格递增才能移动。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示矩阵行列数。

空间复杂度：O(mn)，用于记忆化数组与递归栈。

class Solution {
    private final int[] dx = {1, -1, 0, 0};
    private final int[] dy = {0, 0, 1, -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 i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(matrix, i, j, memo));
            }
        }

        return ans;
    }

    private int dfs(int[][] matrix, int i, int j, int[][] memo) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        int best = 1;
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 || ni >= matrix.length || nj < 0 || nj >= matrix[0].length) {
                continue;
            }
            if (matrix[ni][nj] > matrix[i][j]) {
                best = Math.max(best, 1 + dfs(matrix, ni, nj, memo));
            }
        }

        memo[i][j] = best;
        return best;
    }
}

func longestIncreasingPath(matrix [][]int) int {
	m := len(matrix)
	n := len(matrix[0])
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
	}

	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if memo[i][j] != 0 {
			return memo[i][j]
		}
		best := 1
		for _, d := range dirs {
			ni := i + d[0]
			nj := j + d[1]
			if ni < 0 || ni >= m || nj < 0 || nj >= n {
				continue
			}
			if matrix[ni][nj] > matrix[i][j] {
				val := 1 + dfs(ni, nj)
				if val > best {
					best = val
				}
			}
		}
		memo[i][j] = best
		return best
	}

	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			val := dfs(i, j)
			if val > ans {
				ans = val
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
329. 矩阵中的最长递增路径	困难	DFS + 记忆化
695. 岛屿的最大面积	中等	DFS/BFS
542. 01 矩阵	中等	BFS
130. 被围绕的区域	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/23350850