题目重点：求4邻接且下一格恰好大1的最长路径，利用值顺序构成DAG并返回坐标链。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练4邻接、next=current+1，返回任意最长坐标path；值可重复，但相等格不连接。不是仅next>current的树路径，也不是要求包含1..N所有数。
- 不采用不自洽的示例：如果矩阵缺8，就不能声称存在1..9连续链；是否全值唯一需按实际给定。
解题路线
- 每个合法边从值v到v+1，沿路径值严格上升，因此无环，即使矩阵里有重复值也成立。可按值降序处理动态规划。
- length[cell]=1+max(length[next])，next仅为4邻恰+1；没有合法后继为1。降序保证后继已计算，记录following用于最后重构。
- 遍历所有格找bestStart，不只从最小值或角落开始。值最小处可能孤立，真正长链从别处开始。
- 不要每格保存整条path再拼接，会有多次重复复制；仅长度与一个next，最后O(L)跟指针。
- 可用memo DFS把排序时间降为O(RC)，但递归深度可能长；当前迭代排序基线免递归上限，并如实计排序成本。
手动走一遍
[[1,2,9],[4,3,8],[5,6,7]]可走1→2→3→4→5→6→7→8→9，长度9。[[1,3]]没有+1边，最长1，不能因为3更大就连。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def longest_consecutive_path(grid):
"""Four-neighbor next value exactly current+1, return coordinate path.
Values need not be globally distinct; equal-valued neighbors are not edges.
"""
if not grid or not grid[0]:return []
rows,cols=len(grid),len(grid[0])
if any(len(row)!=cols for row in grid):raise ValueError('rectangular grid')
order=sorted(((r,c) for r in range(rows) for c in range(cols)),key=lambda p:grid[p[0]][p[1]],reverse=True)
lengths={};following={};best=None
for r,c in order:
length=1;successor=None
for dr,dc in ((-1,0),(1,0),(0,-1),(0,1)):
rr,cc=r+dr,c+dc
if 0<=rr<rows and 0<=cc<cols and grid[rr][cc]==grid[r][c]+1 and lengths[rr,cc]+1>length:
length=lengths[rr,cc]+1;successor=(rr,cc)
lengths[r,c]=length;following[r,c]=successor
if best is None or length>lengths[best]:best=(r,c)
path=[]
while best is not None:path.append(best);best=following[best]
return path
复杂度
O(N log N)排序+O(N)4邻DP，N=RC，空间O(N)、输出O(L)。Memo DFS可O(N)时间但需栈/缓存；两实现复杂度不能混写。
易错点与追问
容易失分的边界
- 把大于条件当恰好+1，会输出跳号路径。
- 只从最小值开始，漏掉其他最长起点。
- 坏例缺值仍称全序连续，损害题意可信度。
继续深挖
- 若允许next任意更大，仍是DAG但边与约束不同；仅改边条件即可保持降序DP。
- 若next可以−1或+1，环出现，最长简单路径不能直接套同一递推。
