2021 Google Kickstart A轮第2题测试点2运行时错误求解

错误产生原因 #

• 优先队列残留脏数据：PriorityQueue被定义为全局变量，所有测试用例共用同一个队列实例，前一个测试用例处理后残留的元素会混入下一个测试用例的计算逻辑，测试点2的多测试用例、大数据量场景会直接触发索引越界或逻辑异常。
• 空队列操作触发运行时错误：内层跳过过期元素的逻辑存在时序漏洞，当队列仅剩过期元素时，会在队列已空的状态下继续调用pq.poll()，直接抛出NoSuchElementException，该问题在小数据量的测试点1概率极低，在大数据量的测试点2必然触发。

修复方案 #

• 隔离测试用例数据：将PriorityQueue的初始化逻辑移动到每个测试用例的循环内部，保证每个用例的队列数据独立，避免脏数据干扰。
• 优化过期元素判断逻辑：删除原有风险极高的内层循环poll逻辑，改为单次判断后直接跳过过期元素，从根源上避免空队列调用poll的问题。

修复后代码 #

import java.util.PriorityQueue;
import java.util.Scanner;

class Solution{
    public static void main(String[] args) {
        int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        Scanner scan = new Scanner(System.in);
        int t = 0;
        int[][] arr = new int[305][305];
        int row = 0;
        int col = 0;
        if(scan.hasNextInt()) t = scan.nextInt();
        for(int i = 1;i<=t;i++){
            // 每个测试用例创建独立的优先队列
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>((x,y)->y[0]-x[0]);
            if(scan.hasNextInt()) row = scan.nextInt();
            if(scan.hasNextInt()) col = scan.nextInt();
            long ans = 0;
            for(int j = 0;j<row;j++){
                for(int k = 0;k<col;k++){
                    if(scan.hasNextInt()) arr[j][k] = scan.nextInt();
                    pq.offer(new int[]{arr[j][k],j,k});
                }
            }
            while(!pq.isEmpty()){
                int[] tmp = pq.poll();
                // 过期元素直接跳过，无需循环poll
                if(tmp[0] != arr[tmp[1]][tmp[2]]) continue;
                for(int[] x:dir){
                    int nx = tmp[1] + x[0];
                    int ny = tmp[2] + x[1];
                    if(nx >=0 && nx < row && ny >=0 && ny < col){
                        if(arr[nx][ny] < tmp[0]-1){
                            ans += tmp[0] - 1 - arr[nx][ny];
                            arr[nx][ny] = tmp[0] -1;
                            pq.offer(new int[]{tmp[0]-1, nx, ny});
                        }
                    }
                }
            }
            System.out.println("Case #"+i+": "+ans);
        }
        scan.close();
    }
}

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