329 Longest Increasing Path in a Matrix

ref: 329. 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:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4 The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

分析

这道题显然是一个dfs的backtracking，但是如果不带map记录的话，就需要尝试从每一个点出发去向四个方向explore，显然实在是太暴力了，所以需要带memory。

方式就是用一个Map<Integer, Integer> => Map<startPoint, longestFromThisPoint>来记录，每一个位置都是已经记录了这个点开始最优的解了，所以只要查到map里面包含了这个点，就直接返回了。意味着每一个点就都只计算过一次，所以最后的时间复杂度是O(n*m)

代码

    private static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                res = Math.max(res, explore(matrix, i, j, map));
            }
        }
        return res;
    }

    private int explore(int[][] matrix, int x, int y, Map<Integer, Integer> map) {
        int code = x * matrix[0].length + y;
        if(map.containsKey(code)) {
            return map.get(code);
        }
        int res = 1;
        for(int[] dir: dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if(newX < 0 || newY < 0 || newX >= matrix.length || newY >= matrix[0].length || matrix[newX][newY] <= matrix[x][y]) {
                continue;
            }
            res = Math.max(res, explore(matrix, newX, newY, map) + 1);
        }
        map.put(code, res);
        return res;
    }