329. Longest Increasing Path in a Matrix (Hard)

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Hints

Solutions

class Solution {
    private static final int[][] DIRS = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0
                || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];

        int maxPath = 1;
        // DFS from each cell
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Update the maxLen
                maxPath = Math.max(maxPath, dfs(dp, matrix, i, j));
            }
        }

        return maxPath;
    }

    private int dfs(int[][] dp, int[][] matrix, int row, int col) {
        dp[row][col] = 1;   // 初始化当前值
        for (int[] dir : DIRS) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            if (nextRow < 0 || nextRow >= matrix.length || nextCol < 0 || nextCol >= matrix[0].length
                    || matrix[nextRow][nextCol] <= matrix[row][col]) {
                continue;
            }
            // 如果需要的值还没被计算过,则递归调用 DFS 进行计算
            if (dp[nextRow][nextCol] == 0) {
                dp[nextRow][nextCol] = dfs(dp, matrix, nextRow, nextCol);
            }
            // 计算当前状态信息
            dp[row][col] = Math.max(dp[row][col], dp[nextRow][nextCol] + 1);
        }

        return dp[row][col];
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-04-15 19:17:35

results matching ""

    No results matching ""