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

2026-03-28 HGNULB 约 11 分钟

文章信息 5 个分类 9 个标签

分类

LeetCode 困难 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

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

题意分析

给一个整数矩阵，求其中最长的严格递增路径的长度。路径每一步只能走上下左右四个方向，不能沿对角线，也不能走出矩阵。可以从任意格子出发，到任意格子结束。

「严格递增」是整道题的题眼。它意味着路径上的值一路变大，永远不可能绕回起点——因为回到某个已访问的格子就要求它的值同时大于和小于自己。换句话说，把每个格子看成节点、把「向值更大的邻居走一步」看成一条有向边，得到的一定是一张有向无环图（DAG），问题就是求这张 DAG 上的最长路径。

认出 DAG 这件事直接带来两个结论：第一，不需要 visited 数组，因为不可能成环；第二，DAG 上的最长路径可以做记忆化，而一般图上的最长路径是 NP 难的。这两点是本题从「困难」降为「模板题」的全部原因。

约束里 m, n ≤ 200，格子数最多 $4 \times 10^4$。这个规模允许 $O(mn)$ 甚至带小常数的 $O(mn \log)$，但绝不允许对每个起点各跑一次不带记忆的搜索——那是指数级的。

「从任意格子出发」说明必须以每个格子为起点各试一次，最终答案是所有起点结果的最大值；而不是只从最小值出发。

边界：矩阵至少有一个格子，所以答案至少是 1；相邻格子值相等时不能相互走动（要求严格递增），这是最容易写错的比较符；矩阵可能是一行或一列，越界判断四边都要写全。

解法：动态规划递推

核心思路

最朴素的做法是以每个格子为起点做一次深度优先搜索，沿着值变大的方向一直走，记录走过的最大步数。问题在于同一个格子会被无数条路径反复展开：从不同起点出发的路径可能在中途汇合，汇合之后那一段的搜索完全重复。$200 \times 200$ 的矩阵下这是指数级的开销。

瓶颈的本质在于「从某个格子出发能走多远」这件事只由这个格子自己决定，与「是怎么走到它的」毫无关系。上一段路径再长，也不会改变它往后能延伸的距离。这条无后效性一旦看出来，把结果缓存下来就是水到渠成的事。

于是定义状态：memo[i][j] = 以 (i, j) 为起点的最长严格递增路径的长度（包含 (i, j) 自身）。这个定义有两个要点——「以它为起点」而不是「经过它」，以及「包含自身」所以最小值是 1。

转移方程：$memo[i][j] = 1 + \max{\, memo[x][y] \mid (x,y) \text{ 是四邻且 } matrix[x][y] > matrix[i][j] \,}$；若没有任何一个邻居比自己大，则 memo[i][j] = 1。代码里用「answer 初值取 1，再对每个合法邻居取 max(answer, dfs(x,y) + 1)」来实现，两种写法等价。

不变量是：memo[i][j] != -1 当且仅当 (i, j) 的答案已被完整计算过，且该值不会再改变。-1 表示未计算，而合法答案至少是 1，两者天然可区分。递归函数第一行查表命中就直接返回，这一行把指数级的重复展开压成了「每个格子只算一次」。

因为图是 DAG，递归不会绕回自身，所以不需要「正在访问中」这类第三种状态，也就不需要环检测——这正是严格递增条件送给我们的礼物。

主流程对每个格子调用一次 dfs 并取最大值。已经算过的格子直接命中缓存返回，代价是常数；未算过的格子会顺带把它能到达的整条链算出来并缓存。整体每个格子恰好被真正计算一次，每次检查四个邻居，总代价线性。

解题步骤

建立与矩阵同规模的 memo，整体填 -1。为什么用 -1 而不是 0：合法答案最小是 1（路径至少含自身），0 反而无法与「未计算」区分；若用 0 当哨兵，第一次算出 1 的格子会被误判成还没算过，缓存彻底失效。

对每个格子调用一次 dfs(i, j)，用 answer = max(answer, dfs(i, j)) 汇总。为什么必须遍历所有起点：题目允许从任意格子出发，最长路径的起点未知；只从某一个格子或只从最小值出发都会漏解。

dfs 第一行判 memo[i][j] != -1 则直接返回缓存值。为什么这一行是整道题的性能核心：它保证每个格子的实际计算只发生一次，把指数级搜索压到线性；删掉它算法仍然正确，但会超时。

令局部 answer = 1。为什么初值是 1：路径包含当前格子自身；若初值取 0，所有结果统一少 1，且「四周没有更大邻居」的格子会返回 0，与题意矛盾。

用方向数组 {-1, 0, 1, 0, -1} 依次取出四组偏移。为什么这么写：相邻两项构成一组 (dx, dy)，滑动窗口恰好覆盖上、右、下、左四个方向，比四段 if 更短且天然排除对角线。

对每个邻居先判越界，再判 matrix[x][y] > matrix[i][j]。为什么必须是严格大于：题目要求严格递增，写成 >= 会让相等的两个格子互相递归，DAG 变成有环图，直接栈溢出。为什么先判越界：下标非法时读取 matrix[x][y] 会直接抛异常，两个条件的顺序不能交换。

满足条件时执行 answer = max(answer, dfs(x, y) + 1)。为什么要 +1：dfs(x, y) 返回的是从邻居出发的长度，把当前格子接在它前面就多一格。

循环结束后写入 memo[i][j] = answer 再返回。为什么写在最后：只有把四个方向都试完，answer 才是真正的最大值；中途写入会缓存一个不完整的结果，而缓存一旦写入就不会再被修正。

以 matrix = [[1,2],[4,3]] 走一遍。memo 初始全为 -1，主循环从 (0,0) 开始。

dfs(0,0)（值 1）：缓存未命中，answer = 1。上、左越界。右邻 (0,1) 值 2 > 1，递归。

dfs(0,1)（值 2）：answer = 1。上、右越界；左邻 (0,0) 值 1 不大于 2，跳过；下邻 (1,1) 值 3 > 2，递归。

dfs(1,1)（值 3）：answer = 1。右、下越界；上邻 (0,1) 值 2 不大于 3，跳过；左邻 (1,0) 值 4 > 3，递归。

dfs(1,0)（值 4）：answer = 1。上邻 (0,0) 值 1、右邻 (1,1) 值 3，都不大于 4；左、下越界。写入 memo[1][0] = 1 并返回 1。这是链条的终点——4 是局部最大值，从它出发只能站着不动。

回到 dfs(1,1)：answer = max(1, 1 + 1) = 2，写入 memo[1][1] = 2，返回 2。

回到 dfs(0,1)：answer = max(1, 2 + 1) = 3，写入 memo[0][1] = 3，返回 3。

回到 dfs(0,0)：answer = max(1, 3 + 1) = 4。下邻 (1,0) 值 4 > 1，递归——但 memo[1][0] 已是 1，第一行直接命中返回，answer = max(4, 1 + 1) = 4。写入 memo[0][0] = 4，返回 4。主循环 answer = 4。

主循环继续到 (0,1)、(1,0)、(1,1)：三次调用全部命中缓存，分别返回 3、1、2，都不超过 4。最终答案 4，对应路径 1 → 2 → 3 → 4。

这里能清楚看到缓存的价值：(1,0) 被访问了两次，第二次是常数代价；矩阵越大、路径交汇越多，省下的重复展开越可观。

再看相等值的边界 matrix = [[1,1]]：dfs(0,0) 时右邻值 1 不满足严格大于，直接返回 1；dfs(0,1) 同理。答案是 1，正确。若把比较写成 >=，两个格子会互相递归，memo 永远写不进去，立刻栈溢出。

代码实现

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], 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)$。凭什么：每个格子的 dfs 主体只在缓存未命中时执行一次，此后所有调用都在第一行返回；单次主体检查四个固定方向，是常数工作量。主循环的 $mn$ 次调用中，绝大多数直接命中缓存。

空间复杂度：$O(mn)$。凭什么：memo 与矩阵同规模；递归栈的深度等于最长递增路径的长度，最坏情况下（整个矩阵排成一条蛇形递增链）可达 $mn$，与 memo 同量级。

关键点总结

「严格递增」等价于「图无环」，这一步认知同时免掉了 visited 数组和环检测，也让「DAG 最长路」这个本来 NP 难的问题变得可做——面试时第一句就该说出这个转化。

记忆化的前提是状态无后效性：「从某格出发能走多远」与「怎么走到它」无关。能讲清这一点，才算真正解释了为什么可以缓存，而不是「因为会重复所以加个数组」。

缓存的哨兵值必须不可能是合法答案。这里答案最小为 1，所以用 -1；换成 0 会与「长度 1」混淆，缓存形同虚设。

缓存写入必须发生在所有分支探索完毕之后，中途写入会把不完整的结果永久固化。

记忆化搜索本质上就是「自顶向下的动态规划」，转移方程与自底向上完全一致；本题若改成自底向上，需要按格子值排序或做拓扑排序来确定计算次序，写起来反而更麻烦——这是记忆化优于递推的典型场景。

面试视角：常见追问是「不用递归怎么做」。答案是把它当 DAG 做拓扑排序 + 分层剥离（每轮删掉所有出度为 0 的格子，轮数就是答案），复杂度同为 $O(mn)$ 且没有栈溢出风险，能说出来是明显加分项。

易错点总结

比较写成 >=：matrix = [[1,1]] 中两个格子互相递归，缓存永远写不进去，立刻 StackOverflowError（Go 是 stack exceeded）。

memo 用 0 当未计算标记：matrix = [[1]] 算出答案 1 后仍被判为未计算，缓存失效；在 200 × 200 的递增矩阵上直接退化成指数级搜索并超时。

dfs 里 answer 初值取 0：matrix = [[1]] 返回 0 而正确答案是 1，所有结果统一少 1。

主循环只从某一个格子出发：matrix = [[3,1],[2,4]] 若只从 (0,0) 出发会得到 2（3 → 4），而正确答案是 3（1 → 2 → 4 或 1 → 3 → 4）。

在递归之前就写 memo[i][j]：matrix = [[1,2],[4,3]] 中 (0,0) 会先被缓存成 1，后续所有经过它的查询都读到错误的 1，最终返回 2 而不是 4。

越界判断与取值判断顺序写反：先写 matrix[x][y] > matrix[i][j] 再判越界，matrix = [[1]] 向上探测时访问 matrix[-1][0]，Java 抛越界异常、Go panic。

越界判断漏掉非负一侧：只写 x < m && y < n，同样在 matrix = [[1]] 上崩溃。

额外加了 visited 并在回溯时撤销：matrix = [[1,2],[4,3]] 中 (1,0) 在不同路径下会被反复重新计算，缓存与访问标记互相冲突，退化成指数级搜索；严格递增已经保证无环，visited 是多余的。

主循环的 answer 初值取一个正数：若写成 answer = 1 在本题恰好正确（矩阵非空），但若照搬到允许空矩阵的变体上会返回 1 而不是 0。

误以为可以从全局最小值出发一次搞定：matrix = [[1,2],[4,3]] 的最小值是 1，恰好可行；但 matrix = [[5,1],[6,7]] 的最长路径是 5 → 6 → 7，起点并不是最小值 1。

相似题目

题目	难度	考察点
329. 矩阵中的最长递增路径	困难	与本题同题，可直接套用同一份代码
300. 最长递增子序列	中等	一维版本，元素不要求相邻，因此可用贪心加二分做到 $O(n \log n)$
64. 最小路径和	中等	只能向右向下，计算次序天然确定，不需要记忆化直接递推即可
62. 不同路径	中等	求方案数而非最长长度，状态从取 `max` 变成求和
139. 单词拆分	中等	记忆化的对象是字符串起点，考察如何为非网格状态设计缓存键
210. 课程表 II	中等	显式 DAG 上的拓扑排序，正是本题「不用递归」那条追问路线的模板
576. 出界的路径数	中等	记忆化要多带一维剩余步数，说明状态维度由约束个数决定