如何高效从左下到右上遍历String[][]网格？求时间复杂度优化方案

首先你的代码存在几个明显问题：

• 双重循环遍历了整个网格的所有元素，完全没有实现“取左下角到右上角斜线元素”的逻辑；
• a[x+1][y+1]会直接触发数组越界异常，因为x的取值范围是0 <= x < a.length，x+1会超出数组的行下标范围，同理y+1也会超出列下标范围；
• 时间复杂度是O(m*n)（m为行数，n为列数），这完全没必要，因为我们只需要处理斜线上的元素。

正确逻辑与优化后的实现 #

从左下角到右上角的斜线元素，遍历逻辑应该是：从左下角位置(a.length-1, 0)开始，每次行下标减1、列下标加1，直到行下标小于0或者列下标超出列数范围。这条斜线上的元素总数是min(a.length, a[0].length)，时间复杂度可以降到O(k)（k为斜线上的元素数量，k=min(m,n)），远低于原代码的O(mn)。

优化后的代码如下：

public class prac5 {
    public static String slanting(String[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        int rows = grid.length;
        int cols = grid[0].length;
        // 从左下角开始：行初始为最后一行，列初始为第0列
        int x = rows - 1;
        int y = 0;
        while (x >= 0 && y < cols) {
            sb.append(grid[x][y]);
            x--;
            y++;
        }
        return sb.toString();
    }
}

关于时间复杂度的说明 #

原代码遍历了整个网格的m*n个元素，时间复杂度是O(mn)；优化后的代码只遍历斜线上的k个元素（k=min(m,n)），时间复杂度为O(k)，当m或n较大时，效率提升非常明显。

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