329. Longest Increasing Path in a Matrix

class Solution {
    private int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int longestIncreasingPath(int[][] matrix) {
        int[][] cache = new int[matrix.length][matrix[0].length];
        int max = -1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                max = Math.max(max, dfs(matrix, i, j, cache));
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int row, int col, int[][] cache) {
        if (cache[row][col] != 0) {
            return cache[row][col];
        }
        int maxLength = 1;
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutOfBound(matrix, newRow, newCol) && matrix[row][col] < matrix[newRow][newCol]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, newRow, newCol, cache));
            }
        }
        cache[row][col] = maxLength;
        return cache[row][col];
    }

    private boolean isOutOfBound(int[][] matrix, int row, int col) {
        return row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length;
    }
}

这个DFS是个特殊情况. 因为不会形成cycle. 当时做01 matrix的那道题的时候, 我们用DFS就不太行. 那是因为我们会形成cyclic graph(如果把每个位置看作是一个node的话). 我们从某个node出发, 然后又会回到该node, 回来的前一步这个node需要我们这个node确定答案, 然而我们的那个node却状态还没确定, 需要来到的它的这个node确定. 如果我们用visit来标记走过的node, 那么我们回到原点的时候会发现node已经visit过, 此时会错误地认为这个来过的node已经有了答案, 然而实际情况是没还没有确定.

但是这道题, 由于我们只能从高往低走, 因此不可能有cycle, 如果有cycle那就说明可以从低到高, 这是不符合题意的. 因此这道题就是个DAG(directed, acyclic graph). 于是我们用DFS做就行了. 当然我们对每个位置都进行DFS的时候, 可能某个node会被重复经过, 于是如果我们某个node已经DFS过, 我们记录一下它的结果, 防止重复计算.

时间复杂度: O(m * n) 每个node最多被visit一次.
空间复杂度: O(m * n) 递归需要用栈, memo也需要空间.

class Solution {
    private 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;
        // Get all nodes inDegree count
        int[][] inDegree = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] direction : DIRECTIONS) {
                    int newRow = i + direction[0];
                    int newCol = j + direction[1];
                    if (!isOutOfBound(m, n, newRow, newCol) && matrix[i][j] < matrix[newRow][newCol]) {
                        inDegree[newRow][newCol] += 1;
                    }
                }
            }
        }

        // Get all nodes with no inDegree edges
        Deque<int[]> noDegreeNodes = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (inDegree[i][j] == 0) {
                    noDegreeNodes.offer(new int[] { i, j });
                }
            }
        }

        // Topological Sort
        int length = 0;
        while (!noDegreeNodes.isEmpty()) {
            int size = noDegreeNodes.size();
            for (int i = 0; i < size; i++) {
                int[] currPos = noDegreeNodes.poll();
                for (int[] direction : DIRECTIONS) {
                    int newRow = currPos[0] + direction[0];
                    int newCol = currPos[1] + direction[1];
                    if (!isOutOfBound(m, n, newRow, newCol)
                            && matrix[currPos[0]][currPos[1]] < matrix[newRow][newCol]) {
                        inDegree[newRow][newCol] -= 1;
                        if (inDegree[newRow][newCol] == 0) {
                            noDegreeNodes.offer(new int[] { newRow, newCol });
                        }
                    }
                }
            }
            length += 1;
        }
        return length;

    }

    private boolean isOutOfBound(int rowLength, int colLength, int row, int col) {
        return row < 0 || row >= rowLength || col < 0 || col >= colLength;
    }
}

由于是DAG, 我们要求最长的, 那就是topological sort了. 它就能求最长的. 我们每次在while循环里面的for循环结束, 这意味着我们把此时的leaft node都去除了, 此时length长度就要 + 1.

topological sort都需要存每个node的children是谁, 因为到时候它被移除的话, 看会影响谁, 被影响的chidlren如果没有in degree edges的话, 它就可以被移除了. 因此每个node的in degree的个数也要存. 但是这里我们只存了每个node的in degree个数是谁而没有存每个node的children是谁. 这是因为, 每个node的children只会在自己的四个方向, 当四个方向中有比自己大的, 那它就是我们的children. 因此不需要额外的数据结构去存每个node的children, 这个matrix就能让我们找到每个node的children.

时间复杂度: O(m * n) 每个位置最多被压入queue一次, 再出来一次.
空间复杂度: O(m * n) 我们创建了in degree matrix.