KK's blog

每天积累多一些

0%

LeetCode 329 Longest Increasing Path in a Matrix

Posted on Edited on Disqus:

LeetCode 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.

题目大意：

给定一个整数矩阵，计算其最长递增路径的长度。
从每一个单元格出发，你可以向四个方向移动：左右上下。你不可以沿着对角线移动也不能移出边界。（亦即，环绕是不允许的）。

Floyd解题思路：

这是经典题，类似于LIS题，只要将以每个点为终点的最长路径长度存起来，就可以类推它的邻近点的最长长度（DP）。f(x,y)=max{f(x,y),4个邻近点的f+1}
由于这是求最长路径题且为矩阵，可以考虑按步长计算，就是Floyd的思路，就是先计算步长为1,2一直到所以最长路径长度矩阵长度不再更新为止。
另一个思路也是用矩阵存起每个点最长路径长度，但用DFS搜索，直至这个点的值不为初始值为止，详见书影博客。

注意事项：

  1. 矩阵为空或长度为0
  2. 当任何值没有更新时，Floyd停止计算

Java代码：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public int longestIncreasingPath(int[][] matrix) {
	if (matrix==null || matrix.length==0)
		return 0;
	int[][] path = new int[matrix.length][matrix[0].length];
	for(int i=0;i<matrix.length;i++)
		for(int j=0;j<matrix[0].length;j++)
			path[i][j] = 1;
	
	boolean nextPath = true;
	while(nextPath){
		nextPath = false;
		for(int i=0;i<matrix.length;i++)
			for(int j=0;j<matrix[0].length;j++){
				if(changeCell(matrix, path, i, j))
					nextPath = true;
			}
	}
	
	int max = 1;
	for(int i=0;i<matrix.length;i++)
		for(int j=0;j<matrix[0].length;j++)
			if(path[i][j]>max)
				max = path[i][j];
	return max;
}

public boolean changeCell(int[][] matrix, int[][] path, int i, int j){
	int pre = path[i][j];
	
	if(i-1>=0 && matrix[i-1][j]<matrix[i][j] &&  path[i-1][j]+1>path[i][j])
		path[i][j] = path[i-1][j]+1;
	
	if(i+1<matrix.length && matrix[i+1][j]<matrix[i][j] &&  path[i+1][j]+1>path[i][j])
		path[i][j] = path[i+1][j]+1;
	
	if(j-1>=0 && matrix[i][j-1]<matrix[i][j] &&  path[i][j-1]+1>path[i][j])
		path[i][j] = path[i][j-1]+1;
	
	if(j+1<matrix[0].length && matrix[i][j+1]<matrix[i][j] &&  path[i][j+1]+1>path[i][j])
		path[i][j] = path[i][j+1]+1;
	
	if(pre!=path[i][j])
		return true;
	else return false;
}

算法分析：

k为最长路径长度，时间复杂度为O(kn2)，空间复杂度O(n2)。

DP算法II解题思路(推荐)：

求最值，考虑用DP，但DP的应用条件为有序，所以不妨将所有值排序。
先对所有数的值排序作为新的输入数组，按这个顺序，计算DP，每个点的往前4个方向的DP值+1。

此题递归式跟Floyd是一样的，只是计算方法不同，长度递增vs按排序来计算dp

如题第一个例子, 元祖里第一个为值，后两个为xy坐标
[(1, 2, 1), (1, 2, 2)…]
递归公式：

1
dp[x][y] = dp[x + dx][y + dy] + 1, ifmatrix[x][y] > matrix[x + dx][y + dy]:

最后计算max(dp)

注意事项：

  1. 当递增时，才更新DP，Line 12
  2. matrix比较不是用DP比较，Line 12

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
OFFSET = [(1, 0), (-1, 0), (0, -1), (0, 1)]
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
	nums = [(matrix[i][j], i, j) for i in range(len(matrix)) for j in range(len(matrix[0]))]
	nums.sort()
	res = 0
	dp = [[1] * len(matrix[0]) for _ in range(len(matrix))]
	for num, x, y in nums:
		for _dx, _dy in OFFSET:
			_x, _y = x + _dx, y + _dy
			if _x < 0 or _x >= len(matrix) or _y < 0 or _y >= len(matrix[0]):
				continue
			if matrix[x][y] > matrix[_x][_y]:
				dp[x][y] = max(dp[x][y], dp[_x][_y] + 1)
		res = max(res, dp[x][y])
	return res # max(map(max, dp))

算法分析：

排序是n^2logn^2 = n^2logn, dp计算是n^2
所以时间复杂度为O(n2logn)，空间复杂度O(n2)

算法III解题思路：

这题也可以额用记忆性搜索DFS来解。

Free mock interview