剑指 Offer II 112. 最长递增路径

剑指 Offer II 112. 最长递增路径 #

  • 标签:深度优先搜索、广度优先搜索、图、拓扑排序、记忆化搜索、动态规划
  • 难度:困难

题目大意 #

给定一个 m * n 大小的整数矩阵 matrix。要求:找出其中最长递增路径的长度。

对于每个单元格,可以往上、下、左、右四个方向移动,不能向对角线方向移动或移动到边界外。

解题思路 #

深度优先搜索。使用二维数组 record 存储遍历过的单元格最大路径长度,已经遍历过的单元格就不需要再次遍历了。

代码 #

 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
class Solution:
    max_len = 0
    directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        record = [[0 for _ in range(cols)] for _ in range(rows)]

        def dfs(i, j):
            record[i][j] = 1
            for direction in self.directions:
                new_i, new_j = i + direction[0], j + direction[1]
                if 0 <= new_i < rows and 0 <= new_j < cols and matrix[new_i][new_j] > matrix[i][j]:
                    if record[new_i][new_j] == 0:
                        dfs(new_i, new_j)
                    record[i][j] = max(record[i][j], record[new_i][new_j] + 1)
            self.max_len = max(self.max_len, record[i][j])

        for i in range(rows):
            for j in range(cols):
                if record[i][j] == 0:
                    dfs(i, j)
        return self.max_len
本站总访问量  次  |  您是本站第  位访问者