小旭讲解 LeetCode 329. 矩阵中的最长递增路径leetcode刷题题解

原题

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums =   [    [9,9,4],    [6,6,8],    [2,1,1]  ]   输出: 4   解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

输入: nums =   [    [3,4,5],    [3,2,6],    [2,2,1]  ]   输出: 4   解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

思路 – 记忆化递归

可以直接使用 DFS 进行搜索最长路径，但是时间复杂度是指数级别的，即O(4 ^ {R * C})（R 代表矩阵行数，C 代表矩阵列数），可以通过记忆化递归进行优化。

代码

class Solution { public:     int R, C, ans;     vector<vector<int>> memo;     int d[5] = {0, 1, 0, -1, 0};     int dfs(vector<vector<int>>& matrix, int r, int c) {         if (memo[r][c] > 0) return memo[r][c];         int cans = 1;         for (int di = 0; di < 4; ++di) {             int nr = r + d[di], nc = c + d[di + 1];             if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;             if (matrix[r][c] >= matrix[nr][nc]) continue;             cans = max(cans, 1 + dfs(matrix, nr, nc));         }         return memo[r][c] = cans;     }     int longestIncreasingPath(vector<vector<int>>& matrix) {         // DFS: O(4 ^ (R*C))         // DFS + Memo：O(V + E) V = R * C, E = R * C * 4 => O(R*C)         R = matrix.size();         if (R == 0) return 0;         C = matrix[0].size();         if (C == 0) return 0;         memo = vector<vector<int>>(R, vector<int>(C, 0));         for (int r = 0; r < R; ++r) {             for (int c = 0; c < C; ++c) {                 ans = max(ans, dfs(matrix, r, c));             }         }         return ans;     } };

复杂度分析

时间复杂度：O(R * C) R 代表矩阵行数，C 代表矩阵列数
空间复杂度：O(R * C)

思路 – 拓扑排序

可以想象矩阵中符合题意的路径组成了一个有向无环图，即可通过拓扑排序求解有向无环图的最长路径。

代码

class Solution { public:     int longestIncreasingPath(vector<vector<int>>& matrix) {         // 9 -> 6 -> 2 -> 1 value         // 0    1    1    1 in-degree         int R = matrix.size();         if (R == 0) return 0;         int C = matrix[0].size();         int d[5] = {0, 1, 0, -1, 0};         vector<vector<int>> id = vector<vector<int>>(R, vector<int>(C, 0));         for (int r = 0; r < R; ++r) {             for (int c = 0; c < C; ++c) {                 for (int di = 0; di < 4; ++di) {                     int nr = r + d[di], nc = c + d[di + 1];                     if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;                     if (matrix[nr][nc] > matrix[r][c]) id[r][c]++;                 }             }         }                  queue<pair<int, int>> q;         for (int r = 0; r < R; ++r)             for (int c = 0; c < C; ++c) {                 if (id[r][c] == 0) q.push({r, c});             }         int ans = 0;         while(!q.empty()) {             ++ans;             int l = q.size();             for (int i = 0; i < l; ++i) {                 auto pa = q.front();                 q.pop();                 int r = pa.first, c = pa.second;                 for (int di = 0; di < 4; ++di) {                     int nr = r + d[di], nc = c + d[di + 1];                     if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;                     if (matrix[r][c] <= matrix[nr][nc]) continue;                     --id[nr][nc];                     if (id[nr][nc] == 0) {                         q.push({nr, nc});                     }                 }             }         }         return ans;     } };

复杂度分析

时间复杂度：O(R * C)
空间复杂度：O(R * C)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

小旭讲解 LeetCode 329. 矩阵中的最长递增路径leetcode刷题题解部分资料来自网络，侵权毕设源码联系删除