LeetCode 3459. 最长 V 形对角线段的长度 — Java 实现题目概述- 给定 n × m 的矩阵 grid元素值为 0、1 或 2。- V 形对角线段 规则- 必须从 1 开始。- 后续元素按 2, 0, 2, 0, ... 交替。- 沿四个对角线方向之一移动。- 最多允许一次顺时针 90° 转向。- 返回最长合法路径的长度不存在则返回 0。---核心思路DFS 记忆化搜索状态定义memo[i][j][dir][turn] 表示从位置 (i, j) 出发当前移动方向为 dir是否还能转向 turn0/1时往后能延伸的最长路径长度。四个对角方向按顺时针排列- 0: 右下 (1, 1)- 1: 左下 (1, -1)- 2: 左上 (-1, -1)- 3: 右上 (-1, 1)顺时针 90° 转向dir → (dir 1) % 4目标值计算- 当前值为 1 → 下一步期望 2- 当前值为 2 → 下一步期望 0- 当前值为 0 → 下一步期望 2- 统一公式next grid[i][j] 1 ? 2 : (2 - grid[i][j])递归逻辑1. 沿当前方向前进一步检查是否越界且值匹配。2. 选择一继续直行。3. 选择二若还能转向则顺时针转 90° 后继续。4. 取两者最大值 1当前步。---Java 代码javaclass Solution {// 四个对角方向右下、左下、左上、右上顺时针排列private static final int[][] DIRS {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};// 记忆化数组memo[i][j][dir][turn]// turn1 表示还能转向turn0 表示已转过private int[][][][] memo;private int[][] grid;private int m, n;public int lenOfVDiagonal(int[][] grid) {this.grid grid;this.m grid.length;this.n grid[0].length;// 初始化记忆化数组-1 表示未计算memo new int[m][n][4][2];for (int i 0; i m; i) {for (int j 0; j n; j) {for (int d 0; d 4; d) {memo[i][j][d][0] -1;memo[i][j][d][1] -1;}}}int ans 0;// 枚举所有起点值为 1 的位置for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {// 尝试四个初始方向for (int d 0; d 4; d) {// 1 包含起点本身ans Math.max(ans, dfs(i, j, d, 1) 1);}}}}return ans;}/*** 返回从 (i, j) 出发沿方向 dir是否还能转向 turn 时* 后续路径的最大长度不包含当前点*/private int dfs(int i, int j, int dir, int turn) {// 计算下一步坐标int ni i DIRS[dir][0];int nj j DIRS[dir][1];// 计算下一步期望值int target grid[i][j] 1 ? 2 : (2 - grid[i][j]);// 越界或值不匹配路径终止if (ni 0 || ni m || nj 0 || nj n || grid[ni][nj] ! target) {return 0;}// 检查记忆化if (memo[ni][nj][dir][turn] ! -1) {return memo[ni][nj][dir][turn];}// 选择一继续直行int res dfs(ni, nj, dir, turn);// 选择二若还能转向顺时针转 90° 后继续if (turn 1) {int turnRes dfs(ni, nj, (dir 1) % 4, 0);res Math.max(res, turnRes);}// 记忆化并返回1 包含当前步 ni,njmemo[ni][nj][dir][turn] res 1;return res 1;}}---复杂度分析指标 复杂度 说明时间 O(n × m × 4 × 2) O(nm) 每个状态 (i, j, dir, turn) 只计算一次空间 O(n × m × 4 × 2) O(nm) 记忆化数组---验证示例输入 输出 说明[[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 (0,2)→(1,3)→(2,4) 右转后 (3,3)→(4,2)[[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 (2,3)→(3,2) 右转后 (2,1)→(1,0)[[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 不转向直走 (0,0)→(1,1)→(2,2)→(3,3)→(4,4)[[1]] 1 只有起点---参考来源- 灵茶山艾府题解中的记忆化搜索思路- walkccc 题解中的 C 实现参考- Progiez 的 Java 实现参考