小旭讲解 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/

本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-329-longest-increasing-path-in-a-matrix/
最后修改日期:2020年8月2日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。