小旭讲解 LeetCode 329. 矩阵中的最长递增路径
文章目录

  • 原题
  • 思路 – 记忆化递归
  • 思路 – 拓扑排序
  • 参考

原题

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

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

示例 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刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 329. 矩阵中的最长递增路径leetcode刷题题解