当前位置：首页 > news >正文

从 TLE 到极速通过：Java 算法竞赛大数据量输入优化（BufferedReader + StringTokenizer 详解）

news 2026/7/9 3:27:47

从 TLE 到极速通过：Java 算法竞赛大数据量输入优化（BufferedReader + StringTokenizer 详解）

引言：为什么你的 Java 算法逻辑对了，却依然超时？

很多刚从 LeetCode 转战到蓝桥杯、洛谷、ACM（Codeforces/Nowcoder）等平台的 Java 选手，经常会遇到一个令人沮丧的问题：

“我的算法时间复杂度明明是O ( N ) O(N)O(N)，逻辑也完全没问题，为什么一提交就显示 TLE（超时），甚至 MLE（内存超限）？”

其实，问题往往不在你的算法逻辑上，而是在Java 的输入输出（I/O）性能上。当题目给出的输入数据量达到10 5 10^5105到10 6 10^6106级别时，传统的输入方式往往会成为程序的性能瓶颈。

本文将深度拆解 Java 输入的底层隐患，并带你掌握算法竞赛中不可或缺的"黄金搭档"——BufferedReader与StringTokenizer。

避坑指南：为什么 Scanner 和 split() 是性能杀手？

1. Scanner：便利背后的"沉重代价"

在平时练习中，我们最习惯使用Scanner sc = new Scanner(System.in);。
然而，Scanner的底层实现非常复杂：

它内部使用了大量的正则表达式来匹配不同类型的数据（如nextInt()、nextDouble()）。
正则表达式的解析和匹配是非常消耗 CPU 资源的，导致其运行速度极慢。在大数据量（超过10 5 10^5105）的情况下，光是读入数据就可能耗尽题目的时间限制。

2. split(" “)：隐形的"内存刺客”

为了加速，有些同学换成了BufferedReader，但习惯用split来切割字符串：

// 这是一个常见的性能陷阱String[]arr=br.readLine().split(" ");inta=Integer.parseInt(arr[0]);intb=Integer.parseInt(arr[1]);

这样做同样非常危险：

split方法会在底层创建大量的String[]数组和全新的String子对象。
如果在多组测试数据或循环中使用split，会在短时间内产生海量的垃圾对象，频繁触发 Java 的GC（垃圾回收机制）。这不仅会造成程序卡顿导致TLE，甚至可能直接因为内存占满而导致MLE。
如果输入数据中包含连续的空格，split还会切出空字符串""，从而导致Integer.parseInt抛出异常。

黄金搭档：BufferedReader + StringTokenizer

为了解决上述问题，我们需要引入一套更轻量、更高性能的输入方案。

1. BufferedReader：高效的数据搬运工

BufferedReader的核心在于**“缓冲（Buffer）”**。它不会每次需要一个字符就去和操作系统交互，而是提前在内存中开辟一个大缓冲区（默认 8KB），一次性读入大量字符，后续的读取直接在内存缓冲区中完成，从而极大地减少了系统调用的开销。

2. StringTokenizer：轻量级的"指针切割器"

不同于split会生成庞大的对象数组，StringTokenizer采用了类似于指针移动的轻量级实现：

它直接在原字符串上定位，只在你需要时，通过nextToken()像剥糖果一样依次取出下一个词。
它会自动过滤多余的空格、制表符（Tab）和换行符，容错率极高。
它不需要频繁创建大量字符串垃圾，内存消耗极小。

实战演练：代码的进化史

我们通过一个简单的场景来看看代码是如何一步步优化的。

场景：读入一个N × M N \times MN×M的矩阵，并进行数据处理。

进化前：Scanner 方案（最慢，易超时）

Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[][]matrix=newint[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){matrix[i][j]=sc.nextInt();}}

进化中：BufferedReader + split 方案（有安全隐患，易 MLE）

BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));String[]firstLine=br.readLine().split(" ");intn=Integer.parseInt(firstLine[0]);intm=Integer.parseInt(firstLine[1]);int[][]matrix=newint[n][m];for(inti=0;i<n;i++){String[]row=br.readLine().split(" ");for(intj=0;j<m;j++){matrix[i][j]=Integer.parseInt(row[j]);// 频繁创建数组，GC压力大}}

终极形态：BufferedReader + StringTokenizer（极速且安全）

BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringTokenizerst=newStringTokenizer(br.readLine());intn=Integer.parseInt(st.nextToken());intm=Integer.parseInt(st.nextToken());int[][]matrix=newint[n][m];for(inti=0;i<n;i++){// 每一行重新初始化一个 Tokenizer，读取速度极快st=newStringTokenizer(br.readLine());for(intj=0;j<m;j++){matrix[i][j]=Integer.parseInt(st.nextToken());}}

算法竞赛专属：Java 极速输入输出（Fast I/O）标准模板

在比赛中，为了避免每次都手写StringTokenizer的判断，我们可以将其封装成一个类似Scanner用法的工具类FastReader（或直接命名为Read）。

建议将以下代码保存为你的个人常用模板，在遇到大数据量题目时直接套用：

importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.StringTokenizer;publicclassMain{// ============================================// 核心：FastReader 快速读入模板// ============================================staticclassFastReader{BufferedReaderbr;StringTokenizerst;publicFastReader(){br=newBufferedReader(newInputStreamReader(System.in));}// 核心读取方法：当前行读完时，自动读取下一行Stringnext(){while(st==null||!st.hasMoreTokens()){try{Stringline=br.readLine();if(line==null){returnnull;// 读到文件末尾}st=newStringTokenizer(line);}catch(IOExceptione){e.printStackTrace();}}returnst.nextToken();}// 快捷读取整数intnextInt(){returnInteger.parseInt(next());}// 快捷读取长整数longnextLong(){returnLong.parseLong(next());}// 快捷读取浮点数doublenextDouble(){returnDouble.parseDouble(next());}}publicstaticvoidmain(String[]args){// 实例化快读类FastReadersc=newFastReader();// 像使用 Scanner 一样调用，但速度提升数十倍intn=sc.nextInt();longm=sc.nextLong();System.out.println("读入成功："+n+", "+m);}}

总结与建议

在算法竞赛中，选择合适的工具往往能让你事半功倍：

数据量较小（< 10 4 < 10^4<104）：可以使用Scanner，图个方便和快捷。
数据量中等（10 4 ∼ 10 5 10^4 \sim 10^5104∼105）：推荐换用BufferedReader确保不会超时。
大数据量（> 10 5 > 10^5>105）或多组测试数据：必须使用BufferedReader+StringTokenizer（或使用上述封装好的FastReader模板），保障程序的稳定运行。