329. Longest Increasing Path in a Matrix

, ,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        int[][] memo = new int[m][n];
        int maxLength = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLength = Math.max(maxLength, dfs(matrix, memo, i, j));
            }
        }

        return maxLength;
    }

    private int dfs(int[][] matrix, int[][] memo, int i, int j) {
        int m = matrix.length, n = matrix[0].length;
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        int maxLength = 1;
        for (int[] direction : DIRECTIONS) {
            int nextI = i + direction[0], nextJ = j + direction[1];
            if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && matrix[i][j] < matrix[nextI][nextJ]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, memo, nextI, nextJ));
            }
        }

        memo[i][j] = maxLength;
        return maxLength;
    }
}

BFS + Topological Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        int[][] outDegrees = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] direction : DIRECTIONS) {
                    int nextI = i + direction[0], nextJ = j + direction[1];
                    if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && matrix[i][j] < matrix[nextI][nextJ]) {
                        outDegrees[i][j]++;
                    }
                }
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (outDegrees[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        int maxLength = 0;
        while (!queue.isEmpty()) {
            maxLength++;
            for (int i = queue.size(); i > 0; i--) {
                int[] cell = queue.poll();
                outDegrees[cell[0]][cell[1]]--;
                for (int[] direction : DIRECTIONS) {
                    int preI = cell[0] + direction[0], preJ = cell[1] + direction[1];
                    if (preI >= 0 && preI < m && preJ >= 0 && preJ < n && matrix[preI][preJ] < matrix[cell[0]][cell[1]]) {
                        if (--outDegrees[preI][preJ] == 0) {
                            queue.offer(new int[]{preI, preJ});
                        }
                    }
                }
            }
        }

        return maxLength;
    }
}

References

329. Longest Increasing Path in a Matrix
剑指 Offer II 112. 最长递增路径