Keshawn_lu's Blog

Leetcode 329. 矩阵中的最长递增路径

字数统计: 761阅读时长: 3 min
2020/07/26 Share

题目简介:

给定一个整数矩阵,找出最长递增路径的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。

示例 1:

1
2
3
4
5
6
7
8
输入: nums = 
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

1
2
3
4
5
6
7
8
输入: nums = 
[
[3,4,5],
[3,2,6],
[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

思路:

首先将这个矩阵看做有向图,有向边为数字大的元素指向数字小的元素,这样子问题转化成在有向图中寻找最长路径(关键路径)。

然后计算矩阵每个元素的入度,并将入度为0的元素入队(即从最大的元素开始)

从所有入度为 0 的单元格开始广度优先搜索,每一轮搜索都会遍历当前层的所有单元格,更新其余单元格的入度,并将入度变为 0 的单元格加入下一层搜索(即拓扑排序)。当搜索结束时,搜索的总层数即为矩阵中的最长递增路径的长度。

tips:

  • 计算每个元素的入度或者出度都可以。
  • 注意边界的控制,防止溢出。
  • 可以预先定义一个数组来保存四个方向,即int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }

代码如下:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {

if(matrix.size() == 0 || matrix[0].size() == 0)
return 0;

//每个单元格对应的上下左右四个毗邻单元格
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int row = matrix.size(); //行
int column = matrix[0].size(); //列

//记录每个点的入度
vector<vector<int>> indegree(row, vector<int>(column, 0));

for(int i = 0; i < row; i++){

for(int j = 0; j < column; j++){

for(int k = 0; k < 4; k++){

int newrow = i + directions[k][0];
int newcol = j + directions[k][1];

if(newrow >= 0 && newrow < row && newcol >= 0 && newcol < column && matrix[i][j] > matrix[newrow][newcol])
indegree[i][j]++;
}
}
}

queue<pair<int, int>> qu;

for(int i = 0; i < row; i++){

for(int j = 0; j < column; j++){

//将入度为0的点入队, 即从最大的点开始
if(indegree[i][j] == 0){

qu.push(make_pair(i, j));
}
}
}

int res = 0;
while(!qu.empty()){

res++;
int size = qu.size(); //同一层的一起解决
for(int i = 0; i < size; i++){

pair<int, int> node = qu.front();
int node_row = node.first;
int node_col = node.second;

qu.pop();

for(int k = 0; k < 4; k++){

int newrow = node_row + directions[k][0];
int newcol = node_col + directions[k][1];
if(newrow >= 0 && newrow < row && newcol >= 0 && newcol < column && matrix[node_row][node_col] < matrix[newrow][newcol]){

indegree[newrow][newcol]--; //改变其他点的入度
//将入度为0的点入队
if(indegree[newrow][newcol] == 0)
qu.push(make_pair(newrow, newcol));
}
}
}
}

return res;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: