Hard

题目描述

给定一个 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.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2³¹ - 1

解题思路

这是一个经典的二维矩阵最长路径问题，有两种主要解法：

1. DFS + 记忆化搜索（推荐）

核心思路是对每个位置进行深度优先搜索，计算以该位置为起点的最长递增路径长度。为了避免重复计算，使用记忆化存储每个位置的结果。

  • 对矩阵中的每个位置作为起点进行DFS
  • 在DFS过程中，只能移动到值更大的相邻位置
  • 使用memo数组记录每个位置的最长路径长度，避免重复计算
  • 返回所有起点中的最大值

2. 拓扑排序

将问题转换为有向无环图的拓扑排序问题。每个位置向值更大的相邻位置连边，通过层次遍历计算最长路径。

记忆化搜索的时间复杂度更优，代码也更简洁，是首选解法。关键在于利用递增性质避免成环，确保记忆化的正确性。

代码实现

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> memo(m, vector<int>(n, 0));
        int maxPath = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxPath = max(maxPath, dfs(matrix, i, j, memo));
            }
        }
        
        return maxPath;
    }
    
private:
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>>& memo) {
        if (memo[x][y] != 0) return memo[x][y];
        
        int maxLen = 1;
        for (auto& dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < matrix.size() && ny >= 0 && ny < matrix[0].size() 
                && matrix[nx][ny] > matrix[x][y]) {
                maxLen = max(maxLen, 1 + dfs(matrix, nx, ny, memo));
            }
        }
        
        return memo[x][y] = maxLen;
    }
};

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        memo = [[0] * n for _ in range(m)]
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def dfs(x, y):
            if memo[x][y] != 0:
                return memo[x][y]
            
            max_len = 1
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
                    max_len = max(max_len, 1 + dfs(nx, ny))
            
            memo[x][y] = max_len
            return max_len
        
        max_path = 1
        for i in range(m):
            for j in range(n):
                max_path = max(max_path, dfs(i, j))
        
        return max_path

public class Solution {
    private int[,] memo;
    private int[][] dirs = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0},
        new int[] {0, -1}, new int[] {0, 1}
    };
    
    public int LongestIncreasingPath(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        memo = new int[m, n];
        int maxPath = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxPath = Math.Max(maxPath, Dfs(matrix, i, j));
            }
        }
        
        return maxPath;
    }
    
    private int Dfs(int[][] matrix, int x, int y) {
        if (memo[x, y] != 0) return memo[x, y];
        
        int maxLen = 1;
        foreach (var dir in dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < matrix.Length && ny >= 0 && ny < matrix[0].Length 
                && matrix[nx][ny] > matrix[x][y]) {
                maxLen = Math.Max(maxLen, 1 + Dfs(matrix, nx, ny));
            }
        }
        
        return memo[x, y] = maxLen;
    }
}

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const memo = Array(m).fill().map(() => Array(n).fill(0));
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    function dfs(x, y) {
        if (memo[x][y] !== 0) return memo[x][y];
        
        let maxLen = 1;
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
                maxLen = Math.max(maxLen, 1 + dfs(nx, ny));
            }
        }
        
        return memo[x][y] = maxLen;
    }
    
    let maxPath = 1;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            maxPath = Math.max(maxPath, dfs(i, j));
        }
    }
    
    return maxPath;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型DFS + 记忆化拓扑排序
时间复杂度O(mn)O(mn)
空间复杂度O(mn)O(mn)

时间复杂度说明： 每个位置最多被访问一次，每次访问需要检查4个方向，总体为O(mn) 空间复杂度说明： 需要memo数组存储结果，递归栈最深为mn（最坏情况下路径经过所有位置）

相关题目