Scanner 的读取速度慢于 BufferedReader

LinkedList 的速度慢于 模拟队列

Point[] q 频繁的创建大大增加了时间复杂度，因此放在main函数中只创建一次，而不是放在bfs里面

import java.util.*;
import java.io.*;
class Main{
    static class Point{
        int x, y;
        public Point(int a, int b){
            x = a; y = b;
        }
    }

    private static int n;
    private static int[][] g;
    private static boolean[][] st;
    private static boolean has_lower, has_higher;
    private static Point[] q;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        g = new int[n][n];
        st = new boolean[n][n];
        q = new Point[n*n];
        for(int i = 0; i < n; i++){
            String[] s = br.readLine().split(" ");
            for(int j = 0; j < n; j++){
                g[i][j] = Integer.parseInt(s[j]);
            }
        }

        int peak = 0;
        int valley = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(st[i][j]) continue;
                has_higher = false;
                has_lower = false;
                bfs(i, j);
                if(has_higher == false) peak++;
                if(has_lower == false) valley++;
            }
        }
        bw.write(peak + " " + valley);
        bw.flush();
    }

    private static void bfs(int sx, int sy){
        int hh = 0, tt = -1;
        q[++tt] = new Point(sx, sy);
        st[sx][sy] = true;
        while(hh <= tt){
            Point t = q[hh++];
            for(int i = t.x - 1; i <= t.x + 1; i++){
                for(int j = t.y - 1; j <= t.y + 1; j++){
                    if(i == t.x && j == t.y) continue;
                    if(i < 0 || i >= n || j < 0 || j >= n) continue;
                    if(g[i][j] == g[t.x][t.y]){
                        if(st[i][j]) continue;
                        q[++tt] = new Point(i, j);
                        st[i][j] = true;
                    }else{
                        if(g[i][j] > g[t.x][t.y]) has_higher = true;
                        if(g[i][j] < g[t.x][t.y]) has_lower = true;
                    }
                }
            }
        }
    }
}