题目描述

给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

样例

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

[$\color{red}{9}$, 9, 4]
[$\color{red}{6}$, 6, 8]
[$\color{red}{2}$, $\color{red}{1}$, 4]

算法1

(拓扑排序+BFS) $O(mn)$

1. 找到#个新节点nodes, 从入度0开始, pop出queue, 再将入度减1, 如果入度为0则push进queue, 然后输出结果.
2. 队列queue进行BFS,更新它,直到它空了
   注: 入度定义：则把以顶点v为终点的边的数目，称为v的入度，记为ID

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

参考文献 Discussion Forum

Python 代码

def longestIncreasingPath(self, matrix):
        # idea, use topological sort, search around to find the # of incoming nodes, start with zero indegree with queue, pop from queue, search around and reduce the indegree by 1; push to queue if indegree is 0. output the steps. Time O(mn) and Space O(mn).
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        hmap = {}
        queue = collections.deque()
        for i in range(m):
            for j in range(n):
                cnt = 0
                for dx, dy in directions:
                    x = i + dx
                    y = j + dy
                    if 0 <= x <= m-1 and 0 <= y <= n-1 and matrix[x][y] < matrix[i][j]:
                        cnt += 1
                hmap[(i, j)] = cnt #将点指向#新维度 7.26此处待修改 map point to the # of incoming degree
                if cnt == 0:
                    queue.append((i, j)) # append point (i,j) to queue
        # bfs with queue, and update the step until queue is empty
        step = 0
        while queue:
            size = len(queue)
            for k in range(size):
                i, j = queue.popleft()
                for dx, dy in directions:
                    x = i + dx
                    y = j + dy
                    if 0 <= x <= m-1 and 0 <= y <= n-1 and matrix[x][y] > matrix[i][j] and (x, y) in hmap:
                        hmap[(x, y)] -= 1
                        if hmap[(x, y)] == 0:
                            queue.append((x, y))
            step += 1
        return step

each position is accessible if one of its neighbors is less than itself (dependency), and then here the longest valid dependency chain (topo chain) would be the longest increasing path.

算法2

(DP) $O(？)$

众所周知,找递减反过来就是递增,所以咱们来找递减序列, dp存储之前序列,并选择留下最长的

时间复杂度

参考文献

Python 代码

def longestIncreasingPath(self, matrix):
    def dfs(i, j):
        if not dp[i][j]:
            val = matrix[i][j]
            dp[i][j] = 1 + max(
                dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
                dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
        return dp[i][j]

    if not matrix or not matrix[0]: return 0
    M, N = len(matrix), len(matrix[0])
    dp = [[0] * N for i in range(M)]
    return max(dfs(x, y) for x in range(M) for y in range(N))