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

约 6 分钟
文章信息 5 个分类 9 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 深度优先搜索 广度优先搜索 LCR 矩阵 图 拓扑排序 记忆化

题目描述

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

image-20260929004613619

image-20260929004613620

image-20260929004613621

题意分析

从矩阵任意格子出发，每次只能走到上下左右四邻中数值严格更大的格子，求最长路径包含的格子数。不能斜走、越界或移动到相同数值；没有可走邻居时，当前格子自身仍算长度 1。

解法：记忆化 DFS 复用递增路径

核心思路

[!blue]

将每个格子看作节点，向更大邻居的移动看作有向边。沿边数值始终严格增加，不可能回到已走过的格子，所以图一定无环；搜索时不需要额外记录当前路径的访问状态。

不同起点的路径可能汇合到同一格，而从这一格出发能延伸多长，只取决于它和后面的更大邻居，与到达它的方式无关。因此定义 memo[i][j] 为以 (i, j) 开始的最长递增路径长度，算过后直接复用，避免重复展开相同后缀。

递归先检查缓存，未计算时令局部答案为 1。对每个界内且严格更大的邻居 (x, y)，尝试 dfs(x, y)+1，其中加一表示把当前格子接在邻居路径之前。取四个方向的最大值，全部处理完再存入 memo[i][j]；没有更大邻居时自然得到 1。

代码用 -1 表示未计算，合法结果均至少为 1，所以能与缓存结果区分。0 也可以作为未计算标记，只要初始化和命中条件一起保持一致；这里无需更改现有实现。

最长路径的起点未知，主循环对每个格子调用 dfs 并取最大值。缓存使每个格子的主体只计算一次；严格递增保证递归最终停在没有更大邻居的格子。

解题步骤

  1. 建立同尺寸的 memo，初始化为 -1。
  2. 枚举每个格子作为起点，调用 dfs 并维护全局最大长度。
  3. dfs 命中缓存时直接返回；否则令当前长度为 1。
  4. 枚举四邻，先排除越界，再仅对严格更大的邻居递归，以邻居长度加一更新最大值。
  5. 将完整结果写入当前格子的缓存，再返回。

代码实现

class Solution {
    private int[][] memo;
    private int[][] matrix;
    private int m;
    private int n;

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];

        // -1 表示尚未计算，合法答案最小为 1，两者可区分。
        for (int i = 0; i < m; ++i) {
            Arrays.fill(memo[i], -1);
        }

        int answer = 0;

        // 起点未知，每个格子都要试一次。
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                answer = Math.max(answer, dfs(i, j));
            }
        }

        return answer;
    }

    private int dfs(int i, int j) {
        // 命中缓存，整道题的性能核心。
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        // 路径包含当前格子自身。
        int answer = 1;
        int[] dirs = {
            -1,
            0,
            1,
            0,
            -1
        };

        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k];
            int y = j + dirs[k + 1];

            // 必须严格大于，写成 >= 会让相等的格子互相递归。
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                answer = Math.max(answer, dfs(x, y) + 1);
            }
        }

        // 四个方向都试完才写缓存。
        memo[i][j] = answer;

        return answer;
    }
}

func longestIncreasingPath(matrix [][]int) int {
    m, n := len(matrix), len(matrix[0])
    memo := make([][]int, m)
    // -1 表示尚未计算，合法答案最小为 1，两者可区分。
    for i := range memo {
        memo[i] = make([]int, n)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    answer := -1
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        // 命中缓存，整道题的性能核心。
        if memo[i][j] != -1 {
            return memo[i][j]
        }
        // 路径包含当前格子自身。
        answer := 1
        dirs := []int{
            -1,
            0,
            1,
            0,
            -1,
        }
        for k := 0; k < 4; k++ {
            x, y := i+dirs[k], j+dirs[k+1]
            // 必须严格大于，写成 >= 会让相等的格子互相递归。
            if x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j] {
                answer = max(answer, dfs(x, y)+1)
            }
        }
        // 四个方向都试完才写缓存。
        memo[i][j] = answer
        return answer
    }
    // 起点未知，每个格子都要试一次。
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            answer = max(answer, dfs(i, j))
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(mn)$，每个格子只展开一次，每次检查四个方向，其余调用直接返回缓存。
  • 空间复杂度：$O(mn)$，用于缓存；递归栈最深可达到最长路径长度，最坏也是 $O(mn)$。

关键点总结

[!green]

  • 严格递增保证有向图无环，终止条件由数值关系保证。
  • 缓存的是“从当前格子出发”的剩余最长长度，与此前路径无关。
  • 0 与 -1 都不是合法路径长度，均可作未计算标记，初始化和判断必须一致。
  • 当前格子自身计入长度，必须遍历所有可能的起点。

易错点总结

[!yellow]

  • 只沿严格更大的邻居走，因此图无环；改成 >= 会在等值相邻格之间形成环。
  • 缓存初值与命中判断要一致，0 或 -1 都能作为标记，因为合法路径长度至少为 1。
  • 每个格子都可能是起点，不能只从全局最小值出发；结果包含当前格本身。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 同样利用严格递增关系，本题相邻条件来自网格，每格最优长度需记忆化。
207. 课程表 中等 按数值严格递增方向连边后天然无环，可从有向无环图的拓扑层次理解最长路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/23350850
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！