LeetCode 题解工作台
最长 V 形对角线段的长度
给你一个大小为 n x m 的二维整数矩阵 grid ，其中每个元素的值为 0 、 1 或 2 。 V 形对角线段 定义如下： 线段从 1 开始。 后续元素按照以下无限序列的模式排列： 2, 0, 2, 0, ... 。 该线段： 起始于某个对角方向（左上到右下、右下到左上、右上到左下或左下到右上）…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\text{dfs}(i, j, k, \textit{cnt})$，表示上一个位置为 $(i, j)$，当前方向为 ，剩余可转向次数为 时，返回最长的 V 形对角线段长度。 函数 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个大小为 n x m 的二维整数矩阵 grid，其中每个元素的值为 0、1 或 2。
V 形对角线段 定义如下：
- 线段从
1开始。 - 后续元素按照以下无限序列的模式排列：
2, 0, 2, 0, ...。 - 该线段：
- 起始于某个对角方向（左上到右下、右下到左上、右上到左下或左下到右上）。
- 沿着相同的对角方向继续，保持 序列模式 。
- 在保持 序列模式 的前提下，最多允许 一次顺时针 90 度转向 另一个对角方向。
返回最长的 V 形对角线段 的 长度 。如果不存在有效的线段，则返回 0。
示例 1：
输入： grid = [[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]
输出： 5
解释：
最长的 V 形对角线段长度为 5，路径如下：(0,2) → (1,3) → (2,4)，在 (2,4) 处进行 顺时针 90 度转向 ，继续路径为 (3,3) → (4,2)。
示例 2：
输入： grid = [[2,2,2,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]
输出： 4
解释：
最长的 V 形对角线段长度为 4，路径如下：(2,3) → (3,2)，在 (3,2) 处进行 顺时针 90 度转向 ，继续路径为 (2,1) → (1,0)。
示例 3：
输入： grid = [[1,2,2,2,2],[2,2,2,2,0],[2,0,0,0,0],[0,0,2,2,2],[2,0,0,2,0]]
输出： 5
解释：
最长的 V 形对角线段长度为 5，路径如下：(0,0) → (1,1) → (2,2) → (3,3) → (4,4)。
示例 4：
输入： grid = [[1]]
输出： 1
解释：
最长的 V 形对角线段长度为 1，路径如下：(0,0)。
提示：
n == grid.lengthm == grid[i].length1 <= n, m <= 500grid[i][j]的值为0、1或2。
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示上一个位置为 ，当前方向为 ，剩余可转向次数为 时，返回最长的 V 形对角线段长度。
函数 的执行逻辑如下：
我们首先基于上一个位置以及当前的方向，计算当前得到当前位置 ，然后计算当前目标值 。如果 或 不在矩阵范围内，或者 ，返回 。
否则，我们有两种选择：
- 继续沿着当前方向前进。
- 在当前位置进行顺时针 90 度转向，然后继续前进。
我们可以通过改变方向来实现顺时针 90 度转向。具体来说，如果当前方向为 ，则顺时针 90 度转向后的新方向为 。最后，我们选择这两种选择中的最大值作为当前状态的结果。
在主函数中，我们遍历整个矩阵，对于每个值为 1 的位置，尝试四个方向的搜索，并更新答案。
遍历结束后，返回答案即可。
为了避免重复计算，我们使用记忆化搜索来缓存中间结果。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
@cache
def dfs(i: int, j: int, k: int, cnt: int) -> int:
x, y = i + dirs[k], j + dirs[k + 1]
target = 2 if grid[i][j] == 1 else (2 - grid[i][j])
if not 0 <= x < m or not 0 <= y < n or grid[x][y] != target:
return 0
res = dfs(x, y, k, cnt)
if cnt > 0:
res = max(res, dfs(x, y, (k + 1) % 4, 0))
return 1 + res
m, n = len(grid), len(grid[0])
dirs = (1, 1, -1, -1, 1)
ans = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
for k in range(4):
ans = max(ans, dfs(i, j, k, 1) + 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n _m) because each cell is processed once in both forward and backward DP passes. Space complexity is O(n_ m) for the memoization matrices storing diagonal lengths in both directions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate identifies the DP pattern connecting diagonals and turning points.
- question_mark
Candidate efficiently combines forward and backward memoized paths.
- question_mark
Candidate correctly handles edge cells and ensures proper boundary checks.
常见陷阱
外企场景- error
Forgetting to include the turning point in the total length calculation.
- error
Confusing diagonal directions leading to incorrect segment lengths.
- error
Inefficient recomputation of overlapping diagonals without memoization.
进阶变体
外企场景- arrow_right_alt
Compute longest inverted V-shaped or Λ-shaped segments.
- arrow_right_alt
Find longest diagonal segments without a turn for simpler DP.
- arrow_right_alt
Determine longest segment allowing multiple 90-degree turns.