329. Longest Increasing Path in a Matrix

看了答案，这个topological sort也可以做，但是感觉没这个必要？

二刷 07/2022

Version #1 DFS with Memorization

Time O(MN)

Space O(MN)

Runtime: 9 ms, faster than 95.05% of Java online submissions for Longest Increasing Path in a Matrix.

Memory Usage: 42.3 MB, less than 97.52% of Java online submissions for Longest Increasing Path in a Matrix.

class Solution {

    public int longestIncreasingPath(int[][] matrix) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        Integer[][] dp = new Integer[rows][cols];

        int max = 0;

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                max = Math.max(max, dfs(matrix, dp, y, x));

            }

        }

        return max;

    }

    

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    

    private int dfs(int[][] matrix, Integer[][] dp, int y, int x) {

        if (dp[y][x] != null) {

            return dp[y][x];

        }

        int max = 0;

        for (int i = 0; i < 4; i++) {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (ny < 0 || nx < 0 || ny >= matrix.length || nx >= matrix[0].length) {

                continue;

            }

            if (matrix[ny][nx] > matrix[y][x]) {

                max = Math.max(max, dfs(matrix, dp, ny, nx));

            }

        }

        dp[y][x] = 1 + max;

        return dp[y][x];

    }

}

一刷

DFS + mem
Time O(mn)
Space O(mn)

82.62 %
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        // dp[x][y] -> longest increasing path started from position x,y
        // If its neighbor is larger than curr, get its value and +1
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        Integer[][] mem = new Integer[rows][cols];
        int[] max = new int[1];
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                helper(matrix, x, y, mem, max);
            }
        }
        return max[0];
    }
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, -1, 0, 1};
    private int helper(int[][] matrix, int x, int y, Integer[][] mem, int[] max) {
        if (mem[x][y] != null) {
            return mem[x][y];
        }
        int currMax = 1;
        for (int i = 0; i < 4; i++) {
            int currX = x + dx[i];
            int currY = y + dy[i];
            if (currX >= 0 && currX < matrix.length && currY >= 0 && currY < matrix[0].length
                && matrix[currX][currY] > matrix[x][y]) {
                currMax = Math.max(currMax, 1 + helper(matrix, currX, currY, mem, max));
            }
        }
        mem[x][y] = currMax;
        max[0] = Math.max(max[0], currMax);
        return currMax;
    }
}