Java solution


  • 0
    J

    performance not as good s uses array list to record changed values. but provide a new way of solution.

        public int longestIncreasingPath(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) return 0;
            int m = matrix.length, n = matrix[0].length;
            int[][] dp = new int[m][n];
            ArrayList<int[]> changed = new ArrayList<>(m * n);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = 1;
                    changed.add(new int[]{i, j});
                }
            }
            int max = 1;
            while (changed.size() > 0) {
                ArrayList<int[]> next = new ArrayList<>();
                for (int[] pos : changed) {
                    int i = pos[0], j = pos[1], tmpMax = dp[i][j] + 1;
                    if (i > 0 && matrix[i][j] < matrix[i - 1][j]) {
                        if (tmpMax > dp[i - 1][j]) {
                            dp[i - 1][j] = tmpMax;
                            next.add(new int[]{i - 1, j});
                        }
                    }
                    if (j > 0 && matrix[i][j] < matrix[i][j - 1]) {
                        if (tmpMax > dp[i][j - 1]) {
                            dp[i][j - 1] = tmpMax;
                            next.add(new int[]{i, j - 1});
                        }
                    }
                    if (j < n - 1 && matrix[i][j] < matrix[i][j + 1]) {
                        if (tmpMax > dp[i][j + 1]) {
                            dp[i][j + 1] = tmpMax;
                            next.add(new int[]{i, j + 1});
                        }
                    }
                    if (i < m - 1 && matrix[i][j] < matrix[i + 1][j]) {
                        if (tmpMax > dp[i + 1][j]) {
                            dp[i + 1][j] = tmpMax;
                            next.add(new int[]{i + 1, j});
                        }
                    }
                    max = Math.max(max, dp[i][j]);
                }
                changed = next;
            }
            return max;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.