Longest Increasing Path in a Matrix

Leave a comment

December 19, 2016 by oneOokay

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:我用的是一个void DFS( matrix, int x, int y, int value, ArrayList result): 但是TLE了。因为存在着很多的重复查找。

所以用一个cache matrix来存当前点的max increasing path length,这样在dfs到该点的时候,就可以直接从cache里面读值而不用继续DFS了。

有一个图的解法,暂时没看懂。TODO:

比较通俗易懂的写法是这个:

public int longestIncreasingPath(int[][] matrix) {
   if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return 0;        
int max = 0;
int n = matrix.length;
int m = matrix[0].length;
int[][] cache = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
	max = Math.max(dfs(matrix,  i, j,Integer.MIN_VALUE, cache), max);
}}
return max;
}
    
    private int dfs(int[][] matrix, int row, int col, int value, 
int[][] cache){
        if (row < 0 || row > matrix.length - 1 || col < 0 || col > matrix[0].length - 1){
            return 0;
        }        
        int cur = matrix[row][col];
        if (cur <= value) return 0; //注意这里传入的row和col并不意味着该点符合
increasing path,所以先要判断它是否可以成为increasing path的一个点  
//说明当前点是increasing path的一个点,此时不用继续遍历,直接取cache值。      
        if (cache[row][col] != 0) return cache[row][col];        
        int a = dfs(matrix, row + 1, col, cur, cache) + 1; //注意+1
        int b = dfs(matrix, row, col - 1, cur, cache) + 1; 
        int c = dfs(matrix, row, col + 1, cur, cache) + 1; 
        int d = dfs(matrix, row - 1, col, cur, cache) + 1; 
        int max = Math.max(a, Math.max(b, Math.max(c, d)));
        cache[row][col] = max;//最后更新cache值
        return max;
    }

比较fancy一点的写法是在上下左右遍历那里:

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        	return 0;
        
	int max = 0;
	int n = matrix.length;
	int m = matrix[0].length;
	int[][] cache = new int[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			max = Math.max(dfs(matrix, i, j, cache), max);
		}
	}
	return max;
    }
    private int[][] dirs = 
new int[][]{{0, -1}左移, {0, 1}右移,{-1, 0}下移,{1, 0}上移};
//而且这个dfs函数不需要传入value
    private int dfs(int[][] matrix, int row, int col, int[][] cache){
//这里只有成为increasing path的点才可以继续dfs,所以这里就直接看cache
        if (cache[row][col] != 0) return cache[row][col]; 
        int len = 1;//这里会成为cache的值,所以初始值应该为1
        for(int[] dir : dirs){
            int x = row + dir[0];
            int y = col + dir[1];
            if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[row][col]){
                continue;
            }
            len = Math.max(dfs(matrix, x, y, cache) + 1 , len);
        }
        cache[row][col] = len;
        return len;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: