Row with maximum 1's问题代码运行出现TLE错误如何解决

问题定位 #

导致TLE的核心原因有两个：

• 遍历逻辑存在死循环漏洞：你写的遍历代码中，当判断到a[i][j]==1时，仅更新了行号row，没有对列指针j做左移操作。如果当前行最后一位是1，程序会卡在当前循环分支永远无法退出，直接触发超时。
• 输入效率过低：Java自带的Scanner读取输入的性能较差，当测试用例的矩阵规模较大（比如n、m均大于1000）时，双层循环用Scanner逐元素读取数据也会占用过多时间导致TLE。

修复方案 #

1. 修正核心遍历逻辑 #

原逻辑的设计思路是对的（从矩阵右上角开始遍历，时间复杂度O(n+m)），只需要补全列指针左移的逻辑即可：

int i = 0;
int j = m - 1;
int row = 0;
while(i < n && j >= 0) {
    if(a[i][j] == 1) {
        row = i;  
        j--; // 找到1后左移列指针，找当前行更靠左的1，下一行可以直接从当前列位置判断
    } else {
        i++; // 当前列位置没有1，换下一行判断
    }
}

逻辑修复后，90%以上的TLE问题会直接解决。

2. 输入优化（可选，针对大规模测试用例） #

如果修复逻辑后仍有TLE，将Scanner替换为性能更高的BufferedReader读取输入即可，示例如下：

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
while(t > 0) {
    st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int[][] a = new int[n][m];
    for(int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        for(int j = 0; j < m; j++) {
            a[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    // 上述修正后的遍历逻辑
    System.out.println(row);
    t--;
}

如果输入是所有元素按空格分隔不分行，调整读入逻辑按空格拆分即可。

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