该题解采用了拓扑排序的思想，将矩阵中的每个单元格视为图中的一个节点，如果一个单元格的值小于它相邻的单元格，则在这两个单元格之间存在一条有向边。因此，该问题转化为了找出这个有向图中的最长路径。首先，我们计算每个单元格的出度（即有多少条边从该单元格指向其他单元格），并将出度为0的单元格（即没有任何边指向其他单元格的单元格）加入队列中。然后，我们开始进行拓扑排序，每次从队列中取出一个单元格，并将其相邻单元格的出度减1，如果某个相邻单元格的出度变为0，则将其加入队列中。每次从队列中取出单元格时，路径长度加1。重复这个过程，直到队列为空，此时的路径长度即为最长递增路径的长度。
时间复杂度: O(mn)
空间复杂度: O(mn)
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m = len(matrix)
n = len(matrix[0])
outdegree = [[0 for j in range(n)] for i in range(m)]
queue = deque([])
for i in range(m):
for j in range(n):
now = matrix[i][j]
# 计算每个单元格的出度
if (i - 1 >= 0) and (matrix[i - 1][j] > now):
outdegree[i][j] += 1
if (j - 1 >= 0) and (matrix[i][j - 1] > now):
outdegree[i][j] += 1
if (i + 1 < m) and (matrix[i + 1][j] > now):
outdegree[i][j] += 1
if (j + 1 < n) and (matrix[i][j + 1] > now):
outdegree[i][j] += 1
if not outdegree[i][j]:
queue.append((i, j))
ans = 0
while queue:
ans += 1
for q in range(len(queue)):
i, j = queue.popleft()
now = matrix[i][j]
# 更新相邻单元格的出度
if (i - 1 >= 0) and (matrix[i - 1][j] < now):
outdegree[i - 1][j] -= 1
if not outdegree[i - 1][j]:
queue.append((i - 1, j))
if (j - 1 >= 0) and (matrix[i][j - 1] < now):
outdegree[i][j - 1] -= 1
if not outdegree[i][j - 1]:
queue.append((i, j - 1))
if (i + 1 < m) and (matrix[i + 1][j] < now):
outdegree[i + 1][j] -= 1
if not outdegree[i + 1][j]:
queue.append((i + 1, j))
if (j + 1 < n) and (matrix[i][j + 1] < now):
outdegree[i][j + 1] -= 1
if not outdegree[i][j + 1]:
queue.append((i, j + 1))
return ans
