🌕🌕 329. 矩阵中的最长递增路径

难度: 🌕🌕

问题描述

---

解法 1 - DFS + map

class Solution {
    HashMap<String, Integer> map;
    int row;
    int col;
    public int longestIncreasingPath(int[][] matrix) {
        // 思路：
        // 回溯 + map 保存走过节点的最长递增路径
        row = matrix.length;
        col = matrix[0].length;
        map = new HashMap<>();
        int res = 1;

        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                int cur = mySol(matrix, i, j, -1);
                res = Math.max(res, cur);
                // System.out.println(matrix[i][j] + "  " + cur);
            }
        }

        return res;
    }

    private int mySol(int[][] matrix, int i, int j, int prev) {
        // 递归终止条件
        if(!isValid(i, j)) {
            return 0;
        }
        int cur = matrix[i][j]; // 当前处在的位置对应的 val

        // 尝试往四个方向走
        int res = 0;
        
        if(isValid(i - 1, j) && cur > matrix[i - 1][j]) {
            String key = getKey(i - 1, j);
            if(map.containsKey(key)) {
                res = Math.max(res, map.get(key));
            } else {
                int tmp = mySol(matrix, i - 1, j, cur);
                map.put(key, tmp);
                res = Math.max(res, tmp);
            }
        }
        if(isValid(i + 1, j) && cur > matrix[i + 1][j]) {
            String key = getKey(i + 1, j);
            if(map.containsKey(key)) {
                res = Math.max(res, map.get(key));
            } else {
                int tmp = mySol(matrix, i + 1, j, cur);
                map.put(key, tmp);
                res = Math.max(res, tmp);
            }
        }
        if(isValid(i, j - 1) && cur > matrix[i][j - 1]) {
            String key = getKey(i, j - 1);
            if(map.containsKey(key)) {
                res = Math.max(res, map.get(key));
            } else {
                int tmp = mySol(matrix, i, j - 1, cur);
                map.put(key, tmp);
                res = Math.max(res, tmp);
            }
        }
        if(isValid(i, j + 1) && cur > matrix[i][j + 1]) {
            String key = getKey(i, j + 1);
            if(map.containsKey(key)) {
                res = Math.max(res, map.get(key));
            } else {
                int tmp = mySol(matrix, i, j + 1, cur);
                map.put(key, tmp);
                res = Math.max(res, tmp);
            }
        }

        return res + 1; // 加上当前节点
    }

    private boolean isValid(int i, int j) {
        if(i < 0 || j < 0 || i >= row || j >= col) {
            return false;
        }
        return true;
    }

    private String getKey(int i, int j) {
        return "" + i + "#" + j;
    }
}

---

输出 1

---

解法 2 - DFS + 数组做 map

class Solution {
    int row;
    int col;
    int[][] map;
    int res = 1;
    public int longestIncreasingPath(int[][] matrix) {
        // 思路：
        // 回溯 + map 保存走过节点的最长递增路径
        // 由于 map 存储的 key 值为 [i, j] 坐标，要想保存，需要转 String，可以借助 int[][] 数组发挥 map 的作用
        row = matrix.length;
        col = matrix[0].length;
        map = new int[row][col];

        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(map[i][j] == 0) {
                    // 只要遍历过，至少路径包含单个元素，因此值至少为 1，为 0 说明该点没有遍历过
                    mySol(matrix, i, j, -1);
                } else {
                    // 说明该点已经遍历过，由于 res 在遍历的时候就会比较，因此在遍历周围点的过程中 res 已经得到了更新，因此跳
                }
            }
        }

        return res;
    }

    private int mySol(int[][] matrix, int i, int j, int prev) {
        // 递归终止条件
        if(!isValid(i, j)) {
            return 0;
        }
        int cur = matrix[i][j]; // 当前处在的位置对应的 val

        // 尝试往四个方向走
        int ans = 0;
        
        if(isValid(i - 1, j) && cur > matrix[i - 1][j]) {
            if(map[i - 1][j] > 0) {
                ans = Math.max(ans, map[i - 1][j]);
            } else {
                int tmp = mySol(matrix, i - 1, j, cur);
                map[i - 1][j] = tmp;
                ans = Math.max(ans, tmp);
            }
        }
        if(isValid(i + 1, j) && cur > matrix[i + 1][j]) {
            if(map[i + 1][j] > 0) {
                ans = Math.max(ans, map[i + 1][j]);
            } else {
                int tmp = mySol(matrix, i + 1, j, cur);
                map[i + 1][j] = tmp;
                ans = Math.max(ans, tmp);
            }
        }
        if(isValid(i, j - 1) && cur > matrix[i][j - 1]) {
            if(map[i][j - 1] > 0) {
                ans = Math.max(ans, map[i][j - 1]);
            } else {
                int tmp = mySol(matrix, i, j - 1, cur);
                map[i][j - 1] = tmp;
                ans = Math.max(ans, tmp);
            }
        }
        if(isValid(i, j + 1) && cur > matrix[i][j + 1]) {
           if(map[i][j + 1] > 0) {
                ans = Math.max(ans, map[i][j + 1]);
            } else {
                int tmp = mySol(matrix, i, j + 1, cur);
                map[i][j + 1] = tmp;
                ans = Math.max(ans, tmp);
            }
        }

        ans ++;
        res = Math.max(res, ans);
        return ans; // 加上当前节点
    }

    private boolean isValid(int i, int j) {
        if(i < 0 || j < 0 || i >= row || j >= col) {
            return false;
        }
        return true;
    }
}

---

输出 2

---

解法 3 - dp

class Solution {
    int row;
    int col;
    public int longestIncreasingPath(int[][] matrix) {
        // 思路：
        // 能用 记忆化搜索 的一般能用 dp 实现
        // dp[i][j] = Math.max(top, bottom, left, right) + 1
        // 但问题是，假设当前数组为 示例2 所示，那么我们在计算 3 时，需要提前知道以  4 为起始节点的最长递增路径的长度
        // ∴ dp 起点的访问顺序很重要，应该先计算 val 大的下标处的路径长度，然后依次减小
        // ∴ 需要提前对数组中所有节点根据 val 降序排列
        row = matrix.length;
        col = matrix[0].length;
        List<int[]> list = new ArrayList<>();
        // 将所有元素对应下标 & 值存入 list，然后对 list 排序
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                list.add(new int[]{i, j, matrix[i][j]});
            }
        }
        Collections.sort(list, (a, b) -> {
            return b[2] - a[2]; // 根据 val 降序排序
        });
        int len = list.size();

        int[][] dp = new int[row][col];
        for(int i = 0; i < row; i ++) {
            Arrays.fill(dp[i], 1);
        }
        int res = 1;
        for(int k = 0; k < len; k ++) {
            int[] cur = list.get(k);
            int i = cur[0];
            int j = cur[1];
            int val = cur[2];
            // 往四个方向找
            if(isValid(i - 1, j) && matrix[i][j] < matrix[i - 1][j]) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
            }
            if(isValid(i + 1, j) && matrix[i][j] < matrix[i + 1][j]) {
                dp[i][j] = Math.max(dp[i][j], dp[i + 1][j] + 1);
            }
            if(isValid(i, j - 1) && matrix[i][j] < matrix[i][j - 1]) {
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
            }
            if(isValid(i, j + 1) && matrix[i][j] < matrix[i][j + 1]) {
                dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
            }
            res = Math.max(res, dp[i][j]);
        }
        return res;
    }

    private boolean isValid(int m, int n) {
        if(m < 0 || n < 0 || m >= row || n >= col) {
            return false;
        }
        return true;
    }
}

---

输出 3

---

解法 4 - BFS[拓扑排序]

class Solution {
    int row;
    int col;
    public int longestIncreasingPath(int[][] matrix) {
        // 思路：
        // BFS
        // 定义：
        // 入度 - 其他下标 指向 当前下标，即 当前值 < 相邻某点
        // 入度 == 0 说明 当前点 为局部最高点，相邻节点均不能到达这里
        // 出度 - 当前下标 指向 其他下标，即 当前值 > 相邻某点
        // 出度 == 0 说明 当前点 为局部最低点，无论哪个方向均走不通
        // 假设我们就从 局部最高点 往下遍历，即 入度 == 0 的节点作为初始节点集合
        // 遍历能到达的相邻低点，减去这条与之关联的边，如果发现减去后的相邻点成为了 局部最高点，就将该相邻点也入队
        // 队列中的每轮 就相当于 路径长度 ++
        // ∴ 前提就是先计算出 每个下标处的入度 值
        // 当然，我们也可以从 局部最小点出发，那么就是计算 每个下标的 出度值了
        int[][] monitor = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向
        row = matrix.length;
        col = matrix[0].length;
        int[][] array = new int[row][col];
        // 计算入度值 
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                // 计算四个方向是否有 入度
                int val = matrix[i][j];
                for(int[] cur: monitor) {
                    int x = i + cur[0];
                    int y = j + cur[1];
                    if(isValid(x, y) && matrix[x][y] > val) {
                        array[i][j] ++;
                    }
                }
            }
        }
        LinkedList<int[]> queue = new LinkedList<>();
        // 初始放入 入度 == 0 的节点
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(array[i][j] == 0) {
                    queue.offer(new int[] {i, j, matrix[i][j]});
                }
            }
        }
        int res = 0;
        while(!queue.isEmpty()) {
            res ++;
            int len = queue.size();
            for(int i = 0; i < len; i ++) {
                int[] cur = queue.poll();
                // 减去相邻节点对该节点的入度
                int val = cur[2];
                for(int[] tmp: monitor) {
                    int x = cur[0] + tmp[0];
                    int y = cur[1] + tmp[1];
                    if(isValid(x, y) && matrix[x][y] < val) {
                        array[x][y] --;
                        if(array[x][y] == 0) {
                            queue.offer(new int[]{x, y, matrix[x][y]});
                        }
                    }
                }
            }
        }
        return res;
    }

    private boolean isValid(int i, int j) {
        if(i < 0 || j < 0 || i >= row || j >= col) {
            return false;
        }
        return true;
    }
}

---

输出 4