0329. Longest Increasing Path in a Matrix¶
题目信息¶
- 题号:
0329
- 难度:
Hard
- 主题:
整数矩阵、四邻接路径、严格递增、最长长度
- 原题:
- 重点:
路径可从任意格开始、每步只能上下左右移动、下一格必须严格更大、返回格子数量
题目重述¶
给定整数矩阵 matrix,可以从任意格子作为起点,并反复移动到上、下、左、右相邻格子。每一步到达格子的数值必须严格大于前一个格子的数值;不能对角移动,也不能越过矩阵边界。
返回所有合法路径中包含格子数量的最大值。矩阵行数和列数均位于 [1, 200],每个元素位于 [0, 2^31-1]。相等值不能延长路径;题目只要求最长长度,不要求返回具体坐标序列。
自建示例¶
路径在矩阵中多次转向:
输入:matrix = [
[7, 8, 9],
[6, 1, 10],
[5, 4, 3]
]
输出:8
解释:一条最长路径是 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10,共经过 8 个格子,每一步都移动到四邻格中的更大值。
所有数值相等:
输入:matrix = [[2, 2], [2, 2]]
输出:1
解释:严格递增不允许移动到相等值,因此任意合法路径只能包含起点一个格子。
严格递增关系形成无环图¶
把每个格子看作节点,只向数值更大的四邻格连边。沿边移动时数值严格增加,因此不可能回到已经访问的格子,也就形成一个有向无环图。定义 length(r,c) 为从格子 (r,c) 出发能得到的最长路径长度,则它等于 1 加上所有更大邻居的最大 length;没有更大邻居时就是 1。
同一个格子可能从多个起点被询问,递归结果必须缓存。深搜只在第一次到达时计算,之后直接复用;最后遍历所有格子的出发长度取最大值。相等值不连边,正好对应“严格递增”。
C++ 实现¶
class Solution {
public:
int longestIncreasingPath(
std::vector<std::vector<int>>& matrix) {
int rows = static_cast<int>(matrix.size());
int cols = static_cast<int>(matrix[0].size());
std::vector<std::vector<int>> memo(
rows, std::vector<int>(cols, 0));
const int directions[4][2] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
std::function<int(int, int)> dfs =
[&](int row, int col) -> int {
if (memo[row][col] != 0) return memo[row][col];
int best = 1;
for (const auto& direction : directions) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (nextRow < 0 || nextRow >= rows
|| nextCol < 0 || nextCol >= cols
|| matrix[nextRow][nextCol]
<= matrix[row][col]) {
continue;
}
best = std::max(best,
1 + dfs(nextRow, nextCol));
}
return memo[row][col] = best;
};
int answer = 0;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
answer = std::max(answer, dfs(row, col));
}
}
return answer;
}
};
代码分析¶
递归只沿严格增大的边走,因而不会出现环;memo 使每个格子至多真正展开一次,四个方向的检查总量与格子数成正比。矩阵规模为 R * C 时,时间复杂度为 O(RC),缓存和递归栈额外空间为 ``O(RC)``(递归深度最多为路径长度)。