如何最优遍历二维数组对角线？单词搜索谜题对角线实现咨询

一、垂直方向代码的优化建议 #

你的垂直方向查找逻辑没问题，这里给出几个实用优化点，让代码更健壮、高效：

• 增加边界校验：避免空网格、无效单词长度导致的空指针或逻辑错误
• 提取重复变量：把网格行数、列数提前存储，减少重复计算
• 缩小变量作用域：将consecutiveEmptyFields放在循环内声明，代码更紧凑

优化后的代码：

public List<Coordinate> findPossiblePositionsForWord(Character[][] grid) {
    List<Coordinate> result = new ArrayList<>();
    final int wordLength = getWord().length();
    
    // 边界校验：空网格或单词长度无效直接返回
    if (grid == null || grid.length == 0 || wordLength <= 0) {
        return result;
    }
    int gridRows = grid.length;
    int gridCols = grid[0].length;
    
    for (int column = 0; column < gridCols; column++) {
        int consecutiveEmptyFields = 0;
        // 从下往上遍历列
        for (int row = gridRows - 1; row >= 0; row--) {
            if (grid[row][column] == null) {
                consecutiveEmptyFields++;
                // 只要连续空字段数达标，当前位置就是合法起始点
                if (consecutiveEmptyFields >= wordLength) {
                    result.add(new Coordinate(row, column));
                }
            } else {
                consecutiveEmptyFields = 0;
            }
        }
    }
    return result;
}

二、对角线与反对角线方向的位置查找实现 #

1. 左上到右下（正对角线） #

起始位置需满足：row + 单词长度 - 1 < 网格行数 且 col + 单词长度 - 1 < 网格列数，确保单词不会越界。随后检查对角线路径上的所有格子是否为空。

代码实现：

public List<Coordinate> findPossibleDiagonalPositions(Character[][] grid) {
    List<Coordinate> result = new ArrayList<>();
    final int wordLength = getWord().length();
    if (grid == null || grid.length == 0 || wordLength <= 0) {
        return result;
    }
    int gridRows = grid.length;
    int gridCols = grid[0].length;
    // 计算最大合法起始行/列，避免越界
    int maxStartRow = gridRows - wordLength;
    int maxStartCol = gridCols - wordLength;
    
    for (int row = 0; row <= maxStartRow; row++) {
        for (int col = 0; col <= maxStartCol; col++) {
            boolean canPlace = true;
            // 检查对角线路径的每个格子
            for (int i = 0; i < wordLength; i++) {
                if (grid[row + i][col + i] != null) {
                    canPlace = false;
                    break; // 遇到非空格子直接终止检查
                }
            }
            if (canPlace) {
                result.add(new Coordinate(row, col));
            }
        }
    }
    return result;
}

2. 右上到左下（反对角线） #

起始位置需满足：row + 单词长度 - 1 < 网格行数 且 col - 单词长度 + 1 >= 0。检查路径时，每一步行号+1、列号-1的格子是否为空。

代码实现：

public List<Coordinate> findPossibleAntiDiagonalPositions(Character[][] grid) {
    List<Coordinate> result = new ArrayList<>();
    final int wordLength = getWord().length();
    if (grid == null || grid.length == 0 || wordLength <= 0) {
        return result;
    }
    int gridRows = grid.length;
    int gridCols = grid[0].length;
    int maxStartRow = gridRows - wordLength;
    // 最小合法起始列，避免越界
    int minStartCol = wordLength - 1;
    
    for (int row = 0; row <= maxStartRow; row++) {
        for (int col = minStartCol; col < gridCols; col++) {
            boolean canPlace = true;
            // 检查反对角线路径的每个格子
            for (int i = 0; i < wordLength; i++) {
                if (grid[row + i][col - i] != null) {
                    canPlace = false;
                    break;
                }
            }
            if (canPlace) {
                result.add(new Coordinate(row, col));
            }
        }
    }
    return result;
}

三、关于“更优方案”的说明 #

你提到的双重循环已经是时间复杂度最优的实现，因为必须遍历所有可能的起始位置，时间复杂度为O(MNL)（M=行数，N=列数，L=单词长度）。如果要进一步提升代码可维护性，可以考虑：

• 抽象方向策略：定义Direction接口，包含isValidStartPosition和checkPath方法，让水平、垂直、对角线四种方向的代码复用核心逻辑，减少重复代码
• 预处理网格：如果需要多次查找不同单词的位置，可以提前计算每个位置四个方向的连续空字段长度，后续查找直接O(1)判断是否能放置单词，适合高频查询场景

内容的提问来源于stack exchange，提问作者BJagger