首页 > itarticle > leetcode笔记：329. longest increasing path in a matrix

leetcode笔记：329. longest increasing path in a matrix

admin 11月 14, 2020 0

# Title Difficulty Topic
329 Longest Increasing Path in a Matrix Hard Depth-first Search; Topological Sort; Memoization

Description

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:

1
2
3
4
5
6
7
8
 
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:

1
2
3
4
5
6
7
8
 
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.

1. Brute Force

直接DFS或BFS，时间复杂度$$O(2^{m+n})$$。

2. DFS+memorization (Top-down)

假设dfs(x, y)返回在$$(x, y)$$的最大路径长度。则

$$text{dfs}(x, y) = 1 + max{text{dfs}(nx, ny)},$$

其中，$$(nx, ny)$$表示点$$(x, y)$$的相邻点，同时val[nx][ny] > val[x][y]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
class  {
    private int[][] dirs = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || 
           matrix[0] == null || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] mem = new int[m][n];
        int res = 0;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                res = Math.max(res, dfs(i, j, mem, matrix));
            }
        }
        return res;
    }
    
    public int dfs(int i, int j, int[][] mem, int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if(mem[i][j] > 0) return mem[i][j];
        int max = 1;
        for(int[] dir : dirs) {
            if(i + dir[0] < 0 || i + dir[0] >= m || 
               j + dir[1] < 0 || j + dir[1] >= n || 
               matrix[i+dir[0]][j+dir[1]] <= matrix[i][j]) continue;
            max = Math.max(max, 1 + dfs(i+dir[0], j+dir[1], mem, matrix));
        }
        mem[i][j] = max;
        return max;
    }
}

时间复杂度为$$O(mn)$$，空间复杂度$$O(mn)$$。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能