Longest Increasing Path in a Matrix
你会得到一个由整数构成的网格 matrix，它有 m 行和 n 列，并以行列表的形式给出。路径可以向上、向下、向左或向右移动（不能斜着移动，也不能绕过边缘），每一步都必须到达一个严格更大的值。返回这类路径中最长路径包含的单元格数量。单个单元格也算一条长度为 1 的路径。
函数
- matrixinteger-2d-array
- 由等长行组成的值网格
- 返回值integer
- 最长严格递增路径上的单元格数量
约束条件
1 ≤ m, n ≤ 100，其中m = matrix.length，且n = matrix[i].length- 每一行的长度都相同
n。 0 ≤ matrix[i][j] ≤ 231-1
示例
- 输入
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- 输出
- 7
- 解释
- 路径 3、4、5、6、7、8、9 沿着右侧列向下，沿着底行，再沿着中间列向上到达 9，共有 7 个单元格。从最小值 1 出发，最佳路径有 5 个单元格。
- 输入
- matrix = [[2, 2, 2], [2, 5, 2]]
- 输出
- 2
- 解释
- 相等的值并不算上升，因此没有路径会沿着 2 移动。最好的路径是从 5 周围的三个 2 中任选一个，走到 5 上：2 个格子。
- 输入
- matrix = [[4, 4], [4, 4], [4, 4]]
- 输出
- 1
- 解释
- 每个值都是 4，所以任何地方都不允许移动。每个单元格本身都是一条长度为 1 个单元格的路径，答案是 1。
进阶
你还能返回一条最长路径上的所有单元格，以及这条路径的长度吗？
提示
逐个打开提示，每个都会多透露一点。
路径会不会回到已经经过的单元格？观察沿途数值的变化。
值只会增大，因此路径不会重复经过同一个单元格，而且从某个单元格出发的最长路径与到达该单元格的方式无关。它等于 1 加上从它较大的邻居中最佳的那个出发的最长路径。
每个单元格只计算一次这个数字，并将其存储起来。你可以用自己的栈来实现深度优先搜索，遍历更大的邻居并填入这个数字；也可以从峰值开始，一层一层地剥去网格，并统计层数。
题解
从每个单元格向每个值更大的相邻单元格画一条箭头。沿着每条箭头，数值都会增大，因此箭头链不可能形成循环：这个网格是一个有向无环图，答案就是其中的最长路径。没有循环时，从某个单元格出发的最长路径只取决于该单元格，因此每个单元格只需计算一次：O(m × n)。
沿着每条递增路径前进
结果正确，但无法在最大的测试中运行完毕
思路
从每个单元格开始遍历，沿着每个值更大的相邻单元格分支前进，直到没有可走的分支；最长的遍历路径就是答案。每一步的值都会增大，因此遍历不会返回到某个单元格，也不需要已访问集合。
每次其他遍历经过某个单元格时，都会重新遍历从该单元格开始的路径。在一个 100 × 100 的网格中，如果每个值等于其行号与列号之和，那么每次向右或向下移动，值都会增大，而且有超过 10^58 条遍历路径从左上角出发。
算法
- 对于每个单元格，将（该单元格，1）压入栈中。
- 弹出一个条目（单元格，长度），并用长度更新答案。
- 对于网格内值严格更大的每个相邻单元格，将（相邻单元格，长度 + 1）压入栈中。
- 重复此过程，直到栈为空，然后移至下一个起始单元格。
- 返回遇到的最大长度。
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
answer = 0
for sr in range(rows):
for sc in range(cols):
# Each entry is one path in progress: the cell it ends on and
# how many cells it has.
stack = [(sr, sc, 1)]
while stack:
r, c, length = stack.pop()
answer = max(answer, length)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
stack.append((nr, nc, length + 1))
return answer使用自定义栈的记忆化深度优先搜索
思路
令 best[cell] 表示从该单元格开始的最长递增路径所包含的单元格数：对较大的相邻单元格 nb，取 1 + max(best[nb])；如果没有较大的相邻单元格，则取 1。保存这个值是安全的，因为路径中位于 cell 之前的单元格都更小，不会出现在它之后。在第一个示例中，9 得到 1，8 得到 2，7 得到 3，6 和 2 得到 4，5 和 1 得到 5，4 得到 6，3 得到 7。
一条路径也可能经过全部 10,000 个单元格，递归深度会过大，因此要自己维护一个栈。栈顶单元格会尝试下一个方向，并将一个更大的、尚未完成的相邻单元格压入栈中。四个方向都尝试后，将它弹出并设置它的 best。不需要标记“正在处理”：栈中的每个单元格都比它下方的单元格大。
算法
- 将
best填为 0（表示尚未知），并将每个单元格的方向计数器设为 0。 - 对于
best为 0 的每个单元格，将它压入栈中。 - 在栈顶单元格处，递增它的计数器，并将满足位于网格内、数值更大且尚未完成的那个邻居压入栈中。
- 检查完四个方向后，弹出该单元格，并将
best设为其数值更大的邻居中最大的best加 1；如果没有这样的邻居，则设为 1。 - 返回最大的
best。
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# best[r][c]: cells on the longest increasing path that starts at (r, c).
# 0 means not known yet.
best = [[0] * cols for _ in range(rows)]
# step[r][c]: how many of the 4 directions the search has tried from (r, c).
step = [[0] * cols for _ in range(rows)]
answer = 0
for sr in range(rows):
for sc in range(cols):
if best[sr][sc]:
continue
# Our own stack instead of recursion: a path can be thousands of
# cells long, past Python's limit of 1,000 nested calls.
stack = [(sr, sc)]
while stack:
r, c = stack[-1]
d = step[r][c]
if d < 4:
step[r][c] = d + 1
nr, nc = r + dirs[d][0], c + dirs[d][1]
# The stack only climbs, so a larger neighbour is never on it.
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
stack.append((nr, nc))
continue
# Every larger neighbour is finished: build on the best of them.
stack.pop()
length = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
length = max(length, best[nr][nc] + 1)
best[r][c] = length
answer = max(answer, length)
return answer从峰顶剥离网格
思路
像 Kahn 拓扑排序一样，从最高的值开始向下构建同一张表。峰值，也就是没有更大邻居的单元格，会形成一条包含 1 个单元格的路径：第 1 层。移除所有峰值；失去最后一个更大邻居的单元格就是下一层。重复这个过程，直到网格为空。一个单元格会在其最后一个更大邻居之后的一轮被移除，因此它的层数等于它的 best，层数就是答案。在第一个示例中，各层为 9；8；7；2 和 6；1 和 5；4；3。
统计每个单元格还剩多少个更大的邻居。移除一个单元格时，每个严格小于它的邻居的计数都会减 1，计数变为 0 的单元格会进入下一层。每个单元格只会被移除一次：O(m × n)，无需使用栈。
算法
- 对于每个单元格，统计值比它大的邻居数量。
- 将计数为 0 的所有单元格放入当前层。
- 当当前层不为空时，将层数加 1。对于当前层中的每个单元格，将每个值严格小于它的邻居的计数减 1，并将计数变为 0 的邻居放入下一层。
- 将下一层设为当前层，并重复此过程。
- 返回层数。
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
higher = [[0] * cols for _ in range(rows)]
layer = []
for r in range(rows):
for c in range(cols):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
higher[r][c] += 1
# A peak: no neighbour is larger, so a path from it has one cell.
if higher[r][c] == 0:
layer.append((r, c))
layers = 0
while layer:
layers += 1
next_layer = []
for r, c in layer:
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
higher[nr][nc] -= 1
# Its last larger neighbour is peeled: it is a peak now.
if higher[nr][nc] == 0:
next_layer.append((nr, nc))
layer = next_layer
# Each layer is one step further from a peak; the count is the longest path.
return layers
易错点和边界情况
- 使用
>=而不是>进行比较。遇到两个相邻的 4 时，暴力搜索会来回移动，永远无法结束；记忆化搜索会读取仍在计算中的长度。 - 在 Python 中使用递归。数值沿着 100 × 100 的网格蜿蜒排列时，路径会包含 10,000 个单元格，是默认调用限制 1,000 次的 10 倍。
- 像洪泛填充算法那样跳过已处理的单元格。它们存储的长度正是当前单元格所需的值。
- 只从最小值开始。在第一个示例中，从 1 开始会得到 5 个单元格，但答案是 7，从 3 开始才能得到。
- 将长度设为 0 开始计算。所有值都相同的网格，答案是 1。
常见问题3
矩阵中最长递增路径的时间复杂度是多少？
时间和空间复杂度均为 O(m × n)。可以使用带记忆化的深度优先搜索，也可以逐层剥离：每个单元格只处理一次，并检查它的 4 个邻居。从每个单元格出发尝试所有路径，复杂度会呈指数级增长。
矩阵中的最长递增路径是动态规划问题还是图问题？
两者都是。它是有向无环图中的最长路径，也就是按照拓扑顺序进行动态规划。按值从大到小对单元格排序，也能得到另一种有效顺序，但排序的时间复杂度为 O(m × n × log(m × n))。
这和最长递增子序列有什么不同？
子序列可以跳过元素，但要保持元素的顺序；这里的路径必须移动到相邻的单元格，可以朝四个方向中的任意一个移动。两者中，严格递增的链都不可能绕回自身。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def longestIncreasingPath(matrix):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
预期输出
7