1. 整体设计思路这份助记版到底在解决什么问题1.1 工程开发者与竞赛选手的思维差异先聊点扎心的大实话。大部分工程开发者第一次拿起算法竞赛题脑子里冒出来的第一反应往往是这不就是个排序吗直接Collections.sort不就完事了然后写完之后超时或者更惨编译都没过。不是因为代码写得烂而是因为竞赛场景下的数据结构和工程场景下的数据结构表面上是同一套API实际使用时压根是两套思维。工程上我们最关心的是代码能不能维护、有没有NPE、抽象层够不够清晰所以习惯性new一堆ArrayList、HashMap、StringBuilder层层封装。但竞赛里数据量是几十万甚至上百万级别这时候一个自动装箱的Integer数组和一个原始类型int数组的性能差距就能拉开一倍一个反复拼接String的操作能直接把时间复杂度假性拉满。说白了工程开发是怎么写得优雅竞赛是怎么跑得够快两者都没有错但你要在两套标准之间来回切换时就要有意识地提醒自己。我在带新人刷题的时候经常说一句你不需要把竞赛数据结构想得多么高深它就是你把工程里每天在用的这些容器在极限约束下重新过一遍。ArrayList你熟那你得知道它在竞赛里为什么要换回int[]HashMap你熟那你得知道它在竞赛里需要预先指定容量否则扩容那一瞬间的耗时可能就让你的程序踩线超时。理解这些差异这份助记版的价值才算真正落地。1.2 为什么工程开发者需要一份竞赛专用Java速查先回应一个常见质疑Java在算法竞赛里不是主流C才是那我是不是应该去学C再来打竞赛我的建议是如果你已经有Java工程底子完全没必要为了竞赛重新学一门语言。蓝桥杯、LeetCode周赛、牛客的很多比赛、包括一部分ICPC区域赛的题目Java都是合法参赛语言。真正限制你的从来不是语言而是你对这门语言在极限场景下的行为边界熟不熟悉。Java在竞赛里有三个明显优势值得工程开发者好好利用。第一是标准库极其丰富你在工程里天天用的HashMap、TreeMap、PriorityQueue都是经过大量场景验证的成熟实现不需要像C选手那样小心翼翼地斟酌容器细节。第二是BigInteger的存在遇到大整数运算的题C选手得手写高精度你直接调库就能过。第三是Arrays.sort在基础类型数组上用的是DualPivotQuicksort性能非常能打。但这不意味着没有坑。Java的劣势也很明显自动装箱带来额外的对象开销Scanner读入比C的scanf慢一个数量级输出如果用System.out.println一次一行也会被卡。所以我这份助记版的第一原则是知道什么时候该用标准库什么时候该手写什么时候该换输入输出姿势。这也是工程经验和竞赛经验的交汇点理解了这两套逻辑你的Java算法能力会有质的提升。1.3 助记版的使用方法赛前过一遍赛中当字典这份内容不是教材不负责从零讲解红黑树和堆排序的原理。它更像是一张上战场前的装备检查清单以及战场上临时查配件的工具箱。我自己的习惯是每次参加周赛或者刷题前把这份清单从头到尾过一遍确认自己记得住每个容器的初始容量参数、每个工具类的边界语义、每个容易翻车的性能陷阱。真到了写题的时候大部分数据结构操作是不用过脑子的手速和肌肉记忆才是关键。如果你是刚开始接触竞赛的工程开发者建议把这份助记版当成一个索引。遇到不熟悉的容器去翻Java官方文档或者源码确认细节遇到超时问题回来对照着检查是不是踩了某个性能陷阱。这份助记版里凡是写了实测注意的地方都是我踩过坑之后沉淀下来的结果会比单纯读源码更贴近真实的竞赛场景。2. 基础数据结构选型与初始化细节2.1 数组与List定长数组才是竞赛的原配先统一一个认知竞赛题里绝大多数线性数据结构的场景用原始类型数组就对了List系列反而往往是累赘。原因有两个。第一是自动装箱的开销一个Integer[]数组每个元素都是堆上的一个对象访问时要拆箱存储时要装箱内存占用和CPU开销都成倍上涨。第二个原因是ArrayList的扩容机制它默认容量10超过就扩容1.5倍扩容意味着重新分配内存并复制原数组这个操作在数据量大时非常致命。所以我的默认建议是读入数据时用一个足够大的定长数组比如int[] arr new int[n]n是题目给定的数据量。如果题目没给精确上限就以上限为准多开一点也没关系。int[] arr new int[n]; for (int i 0; i n; i) { arr[i] nextInt(); }这里有几个细节值得注意。Arrays.fill(arr, 0)可以快速把整个数组填充为指定值比手动for循环效率高不少但注意它只对一维数组有效多维数组需要逐维度fill。还有System.arraycopy这是Java里最高效的数组复制方式比Arrays.copyOf原生一层但后者使用更方便竞赛里两者都可以性能差异在小数据量下感知不强。如果你确实需要用动态数组建议提前指定初始容量new ArrayList(n)这样避免多次扩容。还有一个很冷门但好用的技巧用ArrayListInteger存储邻接表时可以这样初始化ListInteger[] adj new ArrayList[n];然后循环里adj[i] new ArrayList();。泛型数组的创建是编译期不允许的这种声明方式可以有效规避检查。2.2 字符串处理String、StringBuilder与char[]的三国演义字符串是算法题里最常见的隐形杀手。工程上写惯了String s a b;的开发者在竞赛里往往会被卡到怀疑人生。原因是String是不可变对象每次拼接都会生成全新的String对象如果在一个循环里拼接n次时间复杂度就是O(n^2)数据量到一万以上就能感受到明显的卡顿。竞赛里的标准方案是StringBuilder。它的核心操作有append、insert、deleteCharAt、setCharAt、reverse、toString基本覆盖了你能想到的所有字符串加工场景。特别注意setCharAt和deleteCharAt这两个是处理竞赛题中原地修改字符串的高频操作。reverse更是做回文类题目时的神器。StringBuilder sb new StringBuilder(); sb.append(abc); sb.reverse(); // cba sb.setCharAt(0, x); // xba sb.deleteCharAt(1); // xa但哪怕StringBuilder也不是万能的。有些题目需要频繁访问字符串中的某个字符比如在循环里做str.charAt(i)charAt本身就是O(1)操作问题不大。但如果你要反复截取子串substring会创建新对象这种情况下更推荐先把字符串转成char[]然后通过数组下标操作。比如判断回文的经典写法就是char[] cs s.toCharArray();之后left和right双指针直接操作数组。我自己做竞赛题时的一个经验是能转char[]就不碰String能用StringBuilder就不做字符串加法。这三者的选择本质上是可变性、性能和便利性的三角取舍理解了这个逻辑你就不会在具体场景下犹豫。2.3 Map与Set家族HashMap、HashSet、TreeMap、TreeSet怎么选工程开发中Map和Set的选型大多数人第一反应是HashMap和HashSet因为平均O(1)复杂度够快。竞赛里也确实是它们最常用但有几个工程习惯需要改掉。第一是HashMap一定要指定初始容量因为默认的16太小数据量大时会反复扩容。公式是初始容量 预期元素数量 / 负载因子(0.75) 1比如预期有10000个元素就写成new HashMap(10000 / 3 1)这能有效减少扩容次数。MapInteger, Integer map new HashMap(n / 3 1); SetInteger set new HashSet(n / 3 1);然后是TreeMap和TreeSet。这两个底层是红黑树操作复杂度是O(log n)但好处是键是有序的可以很方便地取最小键、最大键、比某个键小的最接近键等。工程场景里用得不多竞赛里却是处理区间查询、最近配对类问题的利器。最常用的方法我列一下firstKey()/lastKey()取最小和最大键floorKey(k)小于等于k的最大键ceilingKey(k)大于等于k的最小键lowerKey(k)/higherKey(k)严格小于/大于k的最大/最小键举个例子如果题目的输入是有一堆随机数随时插入、随时查询小于x的最大数用TreeSet加floor方法就是最直白的解法。我在工程里几乎没写过这样的代码但在竞赛题里它经常能比手写平衡树省下巨量时间。还有一个小坑提醒一下HashMap和HashSet的迭代顺序不保证稳定而TreeMap和TreeSet是自然有序的。如果你需要按插入顺序遍历可以用LinkedHashMap这在做LRU缓存的题目时会遇到。3. 高频操作与Collections/Arrays工具类实操要点3.1 排序三种姿势各有各的用处排序是算法竞赛里出现频率最高、也最容易被工程开发者低估的一个操作。工程里写排序基本就是stream.sorted()或者Collections.sort()但在竞赛里你得清楚底层是什么算法、复杂度多少、有没有退化的可能。Java的Arrays.sort(int[])使用的是DualPivotQuicksort平均复杂度O(n log n)在大多数情况下表现很好但它的最坏时间复杂度是O(n^2)。如果题目故意构造了极端数据Java的快排是有可能退化的。而Arrays.sort(Object[])使用的是TimSort即归并排序的优化版本复杂度稳定在O(n log n)代价是需要额外的O(n)空间。所以如果你要对一批对象排序用Arrays.sort没问题对基础类型数组排序默认快排也够用实在不放心就手工转成对象数组。Collections.sort(ListT)底层同样走TimSort。它的另一个优势是支持Comparator自定义排序规则。比如按二维数组的第二列排序Arrays.sort(intervals, (a, b) - a[1] - b[1]);但这里有个大坑当a[1] - b[1]超出int范围时会发生溢出所以更安全的写法是Arrays.sort(intervals, (a, b) - Integer.compare(a[1], b[1]));工程里大家可能不常踩这个坑因为数据量小但竞赛里数据量大了之后这种边界问题分分钟导致答案错误。另外注意Comparator的写法里不要写return a[1] - b[1]除非你确定差值很小。3.2 二分查找你不知道的Arrays.binarySearch返回值Arrays.binarySearch和Collections.binarySearch是工程里很少用、竞赛里几乎每场都会碰到的工具。工程里不常用是因为数据量小不如直接遍历竞赛里常用是因为二分是大量题目的核心优化手段。第一个必须记住的点binarySearch的目标数组或列表必须是有序的否则结果是未定义的。第二个关键点是它的返回值语义——如果找到了返回索引如果没找到返回的是一个插入点的负数再减一的值。也就是说返回值idx -(insertionPoint) - 1其中insertionPoint是目标元素应该插入的位置。int[] arr {1, 3, 5, 7}; int idx Arrays.binarySearch(arr, 4); // 返回 -3因为插入点是下标2-(2)-1 -3这个返回值看着很奇怪但它非常有用你可以通过if (idx 0)判断元素是否存在如果不存在-(idx 1)就是它应该插入的位置。这个技巧在做插入后保持有序类的题目时极其高效。要注意Arrays.binarySearch和Collections.binarySearch的重载版本都支持自定义Comparator但如果你对对象数组使用了Comparator排序那查找时也必须使用相同的Comparator否则查找结果不对。3.3 翻转、填充、拷贝与最值工具类的正确姿势工程开发里Collections.reverse、Arrays.fill、Arrays.copyOf这些方法常被忽略因为业务代码里很少需要手动处理数组底层操作。但在竞赛题里这些高频的小操作能不能写顺手直接决定你解题的上限。Collections.reverse(List? list)可以翻转一个列表。如果你想翻转一个数组最简单的方式是转成Arrays.asList(arr)再调reverse但注意asList返回的列表是定长的不能add和remove。另一个方式是手写双指针交换这在数组翻转的题目里是基础功。Arrays.fill(int[] a, int val)可以快速填充数组用途很广。比如你要初始化一个dp数组为最大值直接用Arrays.fill(dp, Integer.MAX_VALUE / 2)就行注意除以2是为了防止后面加法溢出。拷贝数组常用的有Arrays.copyOf和System.arraycopy。前者会创建一个新数组后者需要你提前准备好目标数组。竞赛里我更常用Arrays.copyOf因为它更简洁比如做扩容数组操作时直接arr Arrays.copyOf(arr, arr.length * 2)。求最值方面Java 8的Stream可以写成Arrays.stream(arr).max().getAsInt()但要注意流操作有额外开销。竞赛里推荐直接手写int max Integer.MIN_VALUE; for (int v : arr) max Math.max(max, v);理由很简单这段代码没有装箱和流框架的开销在大数据量下性能更好。同理Collections.max(list)也是可以直接用的但同样有泛型和装箱的开销。等你写多了就会发现竞赛里很多高频小操作的最佳实现就是手写那几行循环。4. 进阶数据结构堆、双端队列与并查集之间怎么选4.1 PriorityQueue默认小顶堆大顶堆要这样写堆优先队列在竞赛里几乎是每天都会碰到的数据结构比如求TopK、合并K个有序链表、哈夫曼编码、Dijkstra最短路径都是它的主场。Java里的PriorityQueue默认是小顶堆也就是队头元素是最小的。需要大顶堆时许多人会写PriorityQueueInteger pq new PriorityQueue((a, b) - b - a);但这个写法有隐患原因还是整数溢出。更稳的做法是PriorityQueueInteger pq new PriorityQueue(Comparator.reverseOrder());还有一个容易被忽略的操作PriorityQueue的迭代顺序不等于堆的内部顺序。如果你for (int v : pq)遍历得到的并不是从小到大的顺序。想按顺序取出所有元素得用while (!pq.isEmpty()) pq.poll();。这个坑在我刚上手时几乎每场都踩。另外PriorityQueue并不保证相同优先级元素的顺序它是非稳定排序。如果你需要按多个条件排序可以在自定义Comparator里做二次比较。比如先按频率降序、频率相同按值升序PriorityQueueint[] pq new PriorityQueue((a, b) - a[1] ! b[1] ? b[1] - a[1] : a[0] - b[0]);初始化方面new PriorityQueue(n)指定初始容量可以避免resize如果数据量已知建议加上。竞赛里PriorityQueue的时间复杂度是O(log n)的offer和poll相比每次手写堆排序要省心太多。4.2 ArrayDeque与Stack为什么我从不推荐Stack如果你学工程时是从Stack入门的那我劝你趁早忘掉它。Java的Stack继承自Vector所有操作都加锁线程安全这在竞赛里完全是不必要的同步开销。而且Stack的API设计也偏老旧比如peek、push、pop和Deque接口的peekFirst、addFirst、pollFirst相比语义不统一。官方文档里甚至直接建议用ArrayDeque替代Stack。DequeInteger deque new ArrayDeque(); deque.addLast(1); // 入栈 deque.pollLast(); // 出栈 deque.peekLast(); // 看一眼栈顶ArrayDeque的底层是循环数组扩容策略比Stack的Vector更高效而且在单线程场景下没有锁开销实测性能会高出不少。除了当栈用ArrayDeque还是实现双端队列的标准选择。竞赛里ArrayDeque最经典的应用是滑动窗口。比如求每个长度为k的子数组的最大值标准做法是维护一个单调队列用deque存下标保证队头到队尾的下标对应值是递减的。每次窗口滑动时把队头过期的下标弹掉新元素入队时把队尾所有比它小的元素全部弹出这样队头永远是当前窗口的最大值。这个技巧不复杂但写对了能很大提升解题速度。顺便提一句LinkedList也可以当双端队列用但它每个节点是一个独立对象内存开销比ArrayDeque大而且访问不是O(1)的随机访问。除非题目明确要求频繁的中间插入否则我几乎不用LinkedList。4.3 并查集标准库没有的必须手写有一个数据结构在竞赛中极其常用但Java标准库没有现成实现——并查集Union-Find。你用HashSet或HashMap都模拟不了它的核心操作合并两个集合和查询两个元素是否在同一个集合平均摊还复杂度接近O(1)。所以这一节请务必手写并记熟。并查集的核心就三个操作初始化、查找find、合并union。模板如下class UnionFind { int[] parent; int[] rank; UnionFind(int n) { parent new int[n]; rank new int[n]; for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } void union(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; if (rank[fx] rank[fy]) { parent[fx] fy; } else if (rank[fx] rank[fy]) { parent[fy] fx; } else { parent[fy] fx; rank[fx]; } } }这里的rank数组记录的是以当前节点为根的树的近似高度合并时把矮树挂到高树下面可以避免树退化成链表。加上路径压缩之后整体复杂度能压到接近常数级别。工程上你大概率不会手写并查集但在竞赛里它几乎是判断图连通性类题目的默认解法。另一个值得注意的地方是并查集经常配合HashMap做离散化使用当节点编号不是从0到n-1连续的时候先用Map把输入的原始编号映射到连续的索引再跑并查集。模板不变只是预处理多一步。5. 易错点与实战排坑实录5.1 输入输出的性能陷阱Scanner慢到什么程度这是我见过最普遍的性能杀手尤其是从工程转过来的开发者。Scanner用起来确实方便但在竞赛里当输入量达到几十万行时Scanner的nextInt()和nextLine()会慢到让你怀疑人生。我自己实测过用Scanner读10万行数据耗时往往在1秒以上而这还只是输入不算算法本身。破解方案是使用BufferedReader配合StringTokenizer或者更快的StreamTokenizer。前者的代码更直观BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());如果你要写大量输入可以封装一个静态工具方法虽然代码丑一点但性能提升非常明显。我自己习惯在每场竞赛前把这段快读模板写在草稿箱里到时候直接复制粘贴改一下变量名就行。输出端的坑同样不少。System.out.println在输出量大的时候也会成为瓶颈原因是每次调用都有系统调用开销。标准做法是把所有输出拼到一个StringBuilder里最后一次性输出StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { sb.append(ans[i]).append(\n); } System.out.print(sb.toString());这个技巧能把输出时间从原来O(n)次系统调用压缩到1次在大数据量输出时能有几十倍的提升。5.2 整数溢出与类型转换这些坑你一定会踩工程里数据量小int溢出往往不会造成实际影响但竞赛里数据范围动辄10^9甚至10^18溢出问题就成为最大的一类隐性错误。最典型的就是求两个int的均值时写(a b) / 2如果a和b都是10^9级别直接加肯定爆int应该写成a (b - a) / 2。还有求乘积、求组合数、做动态规划时都应该在一开始就把变量定义为long。另一个常见的坑是scala无但Java里需要注意Integer.parseInt和Integer.valueOf的差异。前者返回基础类型int后者返回Integer对象。如果你在泛型容器里反复调用valueOf会频繁进行装箱转换性能会差一些。竞赛里尽量用Integer.parseInt。还有Math.abs(Integer.MIN_VALUE)的结果还是负数因为Integer.MIN_VALUE的绝对值超出了int的表示范围。这个坑在做差值绝对值、坐标距离等题目时很容易踩到。遇到这种情况建议先用long接收再做绝对值或者直接用Math.abs((long) a - b)。5.3 迭代中修改集合并发修改异常的成因与规避在工程代码里如果你写过这样一个循环for (Integer x : list) { if (x 0) list.remove(x); }大概率会抛ConcurrentModificationException。原因是foreach语法糖底层是迭代器迭代器在创建时记录了modCount每次修改集合都会导致modCount变化检测到不一致就抛出异常。竞赛里很多人为了简单直接这样写然后程序崩溃然后一脸茫然。安全的删除方式有几种。最简单的是用Iterator显式删除IteratorInteger it list.iterator(); while (it.hasNext()) { if (it.next() 0) it.remove(); }Java 8后还可以用removeIflist.removeIf(x - x 0);这个写法最简洁性能也不差。还有一个需要警惕的场景在循环里向List添加元素如果只用for (int i 0; i list.size(); i)这种方式倒是没问题因为每次都会重新读取size但如果是foreach循环向ArrayList添加元素极大概率会触发并发修改异常或者死循环因为迭代器不感知列表扩容。最后分享一个小技巧如果你想要快速判断一个元素是否已经被加入某个Set不要在循环里用contains去查List那会是O(n)的。正确的做法是维护一个HashSet每次加入时同时写Set和List判断时直接set.contains(x)这样整体可以保持O(1)的查询复杂度。6. 从助记版到实战我的个人经验与最后的补充这份助记版写到这里核心内容基本都覆盖了。最后再分享一点我个人的使用习惯。每次赛前我不会再从头读一遍所有容器API而是只看三个地方Arrays和Collections工具类的边界语义、PriorityQueue和TreeMap的常用方法签名、以及并查集和快读模板的代码。这三个地方最容易被日常工程经验覆盖也最值得考前确认。还有一个小技巧是用真题检验记忆。每周挑一两道中等难度的算法题限定自己在纯Java環境下用最短时间做出来过程中强制自己不查API文档靠记忆写代码。写完之后再对照源码或文档看哪里有偏差。这个方法我用了很久比反复背API名称有效得多。最后说一句工程开发者的Java功底是你最大的优势而不是包袱。你对代码可读性、边界条件、异常处理的敏感度在竞赛里同样是加分项。别被性能差异吓到掌握了这些常用数据结构后Java在竞赛里足以支撑你拿下绝大多数题目。希望这份助记版能帮你少踩一些坑把时间花在解题思路上而不是和容器API较劲。 Java竞赛数据结构助记版：工程开发者性能优化速查清单
1. 整体设计思路这份助记版到底在解决什么问题1.1 工程开发者与竞赛选手的思维差异先聊点扎心的大实话。大部分工程开发者第一次拿起算法竞赛题脑子里冒出来的第一反应往往是这不就是个排序吗直接Collections.sort不就完事了然后写完之后超时或者更惨编译都没过。不是因为代码写得烂而是因为竞赛场景下的数据结构和工程场景下的数据结构表面上是同一套API实际使用时压根是两套思维。工程上我们最关心的是代码能不能维护、有没有NPE、抽象层够不够清晰所以习惯性new一堆ArrayList、HashMap、StringBuilder层层封装。但竞赛里数据量是几十万甚至上百万级别这时候一个自动装箱的Integer数组和一个原始类型int数组的性能差距就能拉开一倍一个反复拼接String的操作能直接把时间复杂度假性拉满。说白了工程开发是怎么写得优雅竞赛是怎么跑得够快两者都没有错但你要在两套标准之间来回切换时就要有意识地提醒自己。我在带新人刷题的时候经常说一句你不需要把竞赛数据结构想得多么高深它就是你把工程里每天在用的这些容器在极限约束下重新过一遍。ArrayList你熟那你得知道它在竞赛里为什么要换回int[]HashMap你熟那你得知道它在竞赛里需要预先指定容量否则扩容那一瞬间的耗时可能就让你的程序踩线超时。理解这些差异这份助记版的价值才算真正落地。1.2 为什么工程开发者需要一份竞赛专用Java速查先回应一个常见质疑Java在算法竞赛里不是主流C才是那我是不是应该去学C再来打竞赛我的建议是如果你已经有Java工程底子完全没必要为了竞赛重新学一门语言。蓝桥杯、LeetCode周赛、牛客的很多比赛、包括一部分ICPC区域赛的题目Java都是合法参赛语言。真正限制你的从来不是语言而是你对这门语言在极限场景下的行为边界熟不熟悉。Java在竞赛里有三个明显优势值得工程开发者好好利用。第一是标准库极其丰富你在工程里天天用的HashMap、TreeMap、PriorityQueue都是经过大量场景验证的成熟实现不需要像C选手那样小心翼翼地斟酌容器细节。第二是BigInteger的存在遇到大整数运算的题C选手得手写高精度你直接调库就能过。第三是Arrays.sort在基础类型数组上用的是DualPivotQuicksort性能非常能打。但这不意味着没有坑。Java的劣势也很明显自动装箱带来额外的对象开销Scanner读入比C的scanf慢一个数量级输出如果用System.out.println一次一行也会被卡。所以我这份助记版的第一原则是知道什么时候该用标准库什么时候该手写什么时候该换输入输出姿势。这也是工程经验和竞赛经验的交汇点理解了这两套逻辑你的Java算法能力会有质的提升。1.3 助记版的使用方法赛前过一遍赛中当字典这份内容不是教材不负责从零讲解红黑树和堆排序的原理。它更像是一张上战场前的装备检查清单以及战场上临时查配件的工具箱。我自己的习惯是每次参加周赛或者刷题前把这份清单从头到尾过一遍确认自己记得住每个容器的初始容量参数、每个工具类的边界语义、每个容易翻车的性能陷阱。真到了写题的时候大部分数据结构操作是不用过脑子的手速和肌肉记忆才是关键。如果你是刚开始接触竞赛的工程开发者建议把这份助记版当成一个索引。遇到不熟悉的容器去翻Java官方文档或者源码确认细节遇到超时问题回来对照着检查是不是踩了某个性能陷阱。这份助记版里凡是写了实测注意的地方都是我踩过坑之后沉淀下来的结果会比单纯读源码更贴近真实的竞赛场景。2. 基础数据结构选型与初始化细节2.1 数组与List定长数组才是竞赛的原配先统一一个认知竞赛题里绝大多数线性数据结构的场景用原始类型数组就对了List系列反而往往是累赘。原因有两个。第一是自动装箱的开销一个Integer[]数组每个元素都是堆上的一个对象访问时要拆箱存储时要装箱内存占用和CPU开销都成倍上涨。第二个原因是ArrayList的扩容机制它默认容量10超过就扩容1.5倍扩容意味着重新分配内存并复制原数组这个操作在数据量大时非常致命。所以我的默认建议是读入数据时用一个足够大的定长数组比如int[] arr new int[n]n是题目给定的数据量。如果题目没给精确上限就以上限为准多开一点也没关系。int[] arr new int[n]; for (int i 0; i n; i) { arr[i] nextInt(); }这里有几个细节值得注意。Arrays.fill(arr, 0)可以快速把整个数组填充为指定值比手动for循环效率高不少但注意它只对一维数组有效多维数组需要逐维度fill。还有System.arraycopy这是Java里最高效的数组复制方式比Arrays.copyOf原生一层但后者使用更方便竞赛里两者都可以性能差异在小数据量下感知不强。如果你确实需要用动态数组建议提前指定初始容量new ArrayList(n)这样避免多次扩容。还有一个很冷门但好用的技巧用ArrayListInteger存储邻接表时可以这样初始化ListInteger[] adj new ArrayList[n];然后循环里adj[i] new ArrayList();。泛型数组的创建是编译期不允许的这种声明方式可以有效规避检查。2.2 字符串处理String、StringBuilder与char[]的三国演义字符串是算法题里最常见的隐形杀手。工程上写惯了String s a b;的开发者在竞赛里往往会被卡到怀疑人生。原因是String是不可变对象每次拼接都会生成全新的String对象如果在一个循环里拼接n次时间复杂度就是O(n^2)数据量到一万以上就能感受到明显的卡顿。竞赛里的标准方案是StringBuilder。它的核心操作有append、insert、deleteCharAt、setCharAt、reverse、toString基本覆盖了你能想到的所有字符串加工场景。特别注意setCharAt和deleteCharAt这两个是处理竞赛题中原地修改字符串的高频操作。reverse更是做回文类题目时的神器。StringBuilder sb new StringBuilder(); sb.append(abc); sb.reverse(); // cba sb.setCharAt(0, x); // xba sb.deleteCharAt(1); // xa但哪怕StringBuilder也不是万能的。有些题目需要频繁访问字符串中的某个字符比如在循环里做str.charAt(i)charAt本身就是O(1)操作问题不大。但如果你要反复截取子串substring会创建新对象这种情况下更推荐先把字符串转成char[]然后通过数组下标操作。比如判断回文的经典写法就是char[] cs s.toCharArray();之后left和right双指针直接操作数组。我自己做竞赛题时的一个经验是能转char[]就不碰String能用StringBuilder就不做字符串加法。这三者的选择本质上是可变性、性能和便利性的三角取舍理解了这个逻辑你就不会在具体场景下犹豫。2.3 Map与Set家族HashMap、HashSet、TreeMap、TreeSet怎么选工程开发中Map和Set的选型大多数人第一反应是HashMap和HashSet因为平均O(1)复杂度够快。竞赛里也确实是它们最常用但有几个工程习惯需要改掉。第一是HashMap一定要指定初始容量因为默认的16太小数据量大时会反复扩容。公式是初始容量 预期元素数量 / 负载因子(0.75) 1比如预期有10000个元素就写成new HashMap(10000 / 3 1)这能有效减少扩容次数。MapInteger, Integer map new HashMap(n / 3 1); SetInteger set new HashSet(n / 3 1);然后是TreeMap和TreeSet。这两个底层是红黑树操作复杂度是O(log n)但好处是键是有序的可以很方便地取最小键、最大键、比某个键小的最接近键等。工程场景里用得不多竞赛里却是处理区间查询、最近配对类问题的利器。最常用的方法我列一下firstKey()/lastKey()取最小和最大键floorKey(k)小于等于k的最大键ceilingKey(k)大于等于k的最小键lowerKey(k)/higherKey(k)严格小于/大于k的最大/最小键举个例子如果题目的输入是有一堆随机数随时插入、随时查询小于x的最大数用TreeSet加floor方法就是最直白的解法。我在工程里几乎没写过这样的代码但在竞赛题里它经常能比手写平衡树省下巨量时间。还有一个小坑提醒一下HashMap和HashSet的迭代顺序不保证稳定而TreeMap和TreeSet是自然有序的。如果你需要按插入顺序遍历可以用LinkedHashMap这在做LRU缓存的题目时会遇到。3. 高频操作与Collections/Arrays工具类实操要点3.1 排序三种姿势各有各的用处排序是算法竞赛里出现频率最高、也最容易被工程开发者低估的一个操作。工程里写排序基本就是stream.sorted()或者Collections.sort()但在竞赛里你得清楚底层是什么算法、复杂度多少、有没有退化的可能。Java的Arrays.sort(int[])使用的是DualPivotQuicksort平均复杂度O(n log n)在大多数情况下表现很好但它的最坏时间复杂度是O(n^2)。如果题目故意构造了极端数据Java的快排是有可能退化的。而Arrays.sort(Object[])使用的是TimSort即归并排序的优化版本复杂度稳定在O(n log n)代价是需要额外的O(n)空间。所以如果你要对一批对象排序用Arrays.sort没问题对基础类型数组排序默认快排也够用实在不放心就手工转成对象数组。Collections.sort(ListT)底层同样走TimSort。它的另一个优势是支持Comparator自定义排序规则。比如按二维数组的第二列排序Arrays.sort(intervals, (a, b) - a[1] - b[1]);但这里有个大坑当a[1] - b[1]超出int范围时会发生溢出所以更安全的写法是Arrays.sort(intervals, (a, b) - Integer.compare(a[1], b[1]));工程里大家可能不常踩这个坑因为数据量小但竞赛里数据量大了之后这种边界问题分分钟导致答案错误。另外注意Comparator的写法里不要写return a[1] - b[1]除非你确定差值很小。3.2 二分查找你不知道的Arrays.binarySearch返回值Arrays.binarySearch和Collections.binarySearch是工程里很少用、竞赛里几乎每场都会碰到的工具。工程里不常用是因为数据量小不如直接遍历竞赛里常用是因为二分是大量题目的核心优化手段。第一个必须记住的点binarySearch的目标数组或列表必须是有序的否则结果是未定义的。第二个关键点是它的返回值语义——如果找到了返回索引如果没找到返回的是一个插入点的负数再减一的值。也就是说返回值idx -(insertionPoint) - 1其中insertionPoint是目标元素应该插入的位置。int[] arr {1, 3, 5, 7}; int idx Arrays.binarySearch(arr, 4); // 返回 -3因为插入点是下标2-(2)-1 -3这个返回值看着很奇怪但它非常有用你可以通过if (idx 0)判断元素是否存在如果不存在-(idx 1)就是它应该插入的位置。这个技巧在做插入后保持有序类的题目时极其高效。要注意Arrays.binarySearch和Collections.binarySearch的重载版本都支持自定义Comparator但如果你对对象数组使用了Comparator排序那查找时也必须使用相同的Comparator否则查找结果不对。3.3 翻转、填充、拷贝与最值工具类的正确姿势工程开发里Collections.reverse、Arrays.fill、Arrays.copyOf这些方法常被忽略因为业务代码里很少需要手动处理数组底层操作。但在竞赛题里这些高频的小操作能不能写顺手直接决定你解题的上限。Collections.reverse(List? list)可以翻转一个列表。如果你想翻转一个数组最简单的方式是转成Arrays.asList(arr)再调reverse但注意asList返回的列表是定长的不能add和remove。另一个方式是手写双指针交换这在数组翻转的题目里是基础功。Arrays.fill(int[] a, int val)可以快速填充数组用途很广。比如你要初始化一个dp数组为最大值直接用Arrays.fill(dp, Integer.MAX_VALUE / 2)就行注意除以2是为了防止后面加法溢出。拷贝数组常用的有Arrays.copyOf和System.arraycopy。前者会创建一个新数组后者需要你提前准备好目标数组。竞赛里我更常用Arrays.copyOf因为它更简洁比如做扩容数组操作时直接arr Arrays.copyOf(arr, arr.length * 2)。求最值方面Java 8的Stream可以写成Arrays.stream(arr).max().getAsInt()但要注意流操作有额外开销。竞赛里推荐直接手写int max Integer.MIN_VALUE; for (int v : arr) max Math.max(max, v);理由很简单这段代码没有装箱和流框架的开销在大数据量下性能更好。同理Collections.max(list)也是可以直接用的但同样有泛型和装箱的开销。等你写多了就会发现竞赛里很多高频小操作的最佳实现就是手写那几行循环。4. 进阶数据结构堆、双端队列与并查集之间怎么选4.1 PriorityQueue默认小顶堆大顶堆要这样写堆优先队列在竞赛里几乎是每天都会碰到的数据结构比如求TopK、合并K个有序链表、哈夫曼编码、Dijkstra最短路径都是它的主场。Java里的PriorityQueue默认是小顶堆也就是队头元素是最小的。需要大顶堆时许多人会写PriorityQueueInteger pq new PriorityQueue((a, b) - b - a);但这个写法有隐患原因还是整数溢出。更稳的做法是PriorityQueueInteger pq new PriorityQueue(Comparator.reverseOrder());还有一个容易被忽略的操作PriorityQueue的迭代顺序不等于堆的内部顺序。如果你for (int v : pq)遍历得到的并不是从小到大的顺序。想按顺序取出所有元素得用while (!pq.isEmpty()) pq.poll();。这个坑在我刚上手时几乎每场都踩。另外PriorityQueue并不保证相同优先级元素的顺序它是非稳定排序。如果你需要按多个条件排序可以在自定义Comparator里做二次比较。比如先按频率降序、频率相同按值升序PriorityQueueint[] pq new PriorityQueue((a, b) - a[1] ! b[1] ? b[1] - a[1] : a[0] - b[0]);初始化方面new PriorityQueue(n)指定初始容量可以避免resize如果数据量已知建议加上。竞赛里PriorityQueue的时间复杂度是O(log n)的offer和poll相比每次手写堆排序要省心太多。4.2 ArrayDeque与Stack为什么我从不推荐Stack如果你学工程时是从Stack入门的那我劝你趁早忘掉它。Java的Stack继承自Vector所有操作都加锁线程安全这在竞赛里完全是不必要的同步开销。而且Stack的API设计也偏老旧比如peek、push、pop和Deque接口的peekFirst、addFirst、pollFirst相比语义不统一。官方文档里甚至直接建议用ArrayDeque替代Stack。DequeInteger deque new ArrayDeque(); deque.addLast(1); // 入栈 deque.pollLast(); // 出栈 deque.peekLast(); // 看一眼栈顶ArrayDeque的底层是循环数组扩容策略比Stack的Vector更高效而且在单线程场景下没有锁开销实测性能会高出不少。除了当栈用ArrayDeque还是实现双端队列的标准选择。竞赛里ArrayDeque最经典的应用是滑动窗口。比如求每个长度为k的子数组的最大值标准做法是维护一个单调队列用deque存下标保证队头到队尾的下标对应值是递减的。每次窗口滑动时把队头过期的下标弹掉新元素入队时把队尾所有比它小的元素全部弹出这样队头永远是当前窗口的最大值。这个技巧不复杂但写对了能很大提升解题速度。顺便提一句LinkedList也可以当双端队列用但它每个节点是一个独立对象内存开销比ArrayDeque大而且访问不是O(1)的随机访问。除非题目明确要求频繁的中间插入否则我几乎不用LinkedList。4.3 并查集标准库没有的必须手写有一个数据结构在竞赛中极其常用但Java标准库没有现成实现——并查集Union-Find。你用HashSet或HashMap都模拟不了它的核心操作合并两个集合和查询两个元素是否在同一个集合平均摊还复杂度接近O(1)。所以这一节请务必手写并记熟。并查集的核心就三个操作初始化、查找find、合并union。模板如下class UnionFind { int[] parent; int[] rank; UnionFind(int n) { parent new int[n]; rank new int[n]; for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } void union(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; if (rank[fx] rank[fy]) { parent[fx] fy; } else if (rank[fx] rank[fy]) { parent[fy] fx; } else { parent[fy] fx; rank[fx]; } } }这里的rank数组记录的是以当前节点为根的树的近似高度合并时把矮树挂到高树下面可以避免树退化成链表。加上路径压缩之后整体复杂度能压到接近常数级别。工程上你大概率不会手写并查集但在竞赛里它几乎是判断图连通性类题目的默认解法。另一个值得注意的地方是并查集经常配合HashMap做离散化使用当节点编号不是从0到n-1连续的时候先用Map把输入的原始编号映射到连续的索引再跑并查集。模板不变只是预处理多一步。5. 易错点与实战排坑实录5.1 输入输出的性能陷阱Scanner慢到什么程度这是我见过最普遍的性能杀手尤其是从工程转过来的开发者。Scanner用起来确实方便但在竞赛里当输入量达到几十万行时Scanner的nextInt()和nextLine()会慢到让你怀疑人生。我自己实测过用Scanner读10万行数据耗时往往在1秒以上而这还只是输入不算算法本身。破解方案是使用BufferedReader配合StringTokenizer或者更快的StreamTokenizer。前者的代码更直观BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());如果你要写大量输入可以封装一个静态工具方法虽然代码丑一点但性能提升非常明显。我自己习惯在每场竞赛前把这段快读模板写在草稿箱里到时候直接复制粘贴改一下变量名就行。输出端的坑同样不少。System.out.println在输出量大的时候也会成为瓶颈原因是每次调用都有系统调用开销。标准做法是把所有输出拼到一个StringBuilder里最后一次性输出StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { sb.append(ans[i]).append(\n); } System.out.print(sb.toString());这个技巧能把输出时间从原来O(n)次系统调用压缩到1次在大数据量输出时能有几十倍的提升。5.2 整数溢出与类型转换这些坑你一定会踩工程里数据量小int溢出往往不会造成实际影响但竞赛里数据范围动辄10^9甚至10^18溢出问题就成为最大的一类隐性错误。最典型的就是求两个int的均值时写(a b) / 2如果a和b都是10^9级别直接加肯定爆int应该写成a (b - a) / 2。还有求乘积、求组合数、做动态规划时都应该在一开始就把变量定义为long。另一个常见的坑是scala无但Java里需要注意Integer.parseInt和Integer.valueOf的差异。前者返回基础类型int后者返回Integer对象。如果你在泛型容器里反复调用valueOf会频繁进行装箱转换性能会差一些。竞赛里尽量用Integer.parseInt。还有Math.abs(Integer.MIN_VALUE)的结果还是负数因为Integer.MIN_VALUE的绝对值超出了int的表示范围。这个坑在做差值绝对值、坐标距离等题目时很容易踩到。遇到这种情况建议先用long接收再做绝对值或者直接用Math.abs((long) a - b)。5.3 迭代中修改集合并发修改异常的成因与规避在工程代码里如果你写过这样一个循环for (Integer x : list) { if (x 0) list.remove(x); }大概率会抛ConcurrentModificationException。原因是foreach语法糖底层是迭代器迭代器在创建时记录了modCount每次修改集合都会导致modCount变化检测到不一致就抛出异常。竞赛里很多人为了简单直接这样写然后程序崩溃然后一脸茫然。安全的删除方式有几种。最简单的是用Iterator显式删除IteratorInteger it list.iterator(); while (it.hasNext()) { if (it.next() 0) it.remove(); }Java 8后还可以用removeIflist.removeIf(x - x 0);这个写法最简洁性能也不差。还有一个需要警惕的场景在循环里向List添加元素如果只用for (int i 0; i list.size(); i)这种方式倒是没问题因为每次都会重新读取size但如果是foreach循环向ArrayList添加元素极大概率会触发并发修改异常或者死循环因为迭代器不感知列表扩容。最后分享一个小技巧如果你想要快速判断一个元素是否已经被加入某个Set不要在循环里用contains去查List那会是O(n)的。正确的做法是维护一个HashSet每次加入时同时写Set和List判断时直接set.contains(x)这样整体可以保持O(1)的查询复杂度。6. 从助记版到实战我的个人经验与最后的补充这份助记版写到这里核心内容基本都覆盖了。最后再分享一点我个人的使用习惯。每次赛前我不会再从头读一遍所有容器API而是只看三个地方Arrays和Collections工具类的边界语义、PriorityQueue和TreeMap的常用方法签名、以及并查集和快读模板的代码。这三个地方最容易被日常工程经验覆盖也最值得考前确认。还有一个小技巧是用真题检验记忆。每周挑一两道中等难度的算法题限定自己在纯Java環境下用最短时间做出来过程中强制自己不查API文档靠记忆写代码。写完之后再对照源码或文档看哪里有偏差。这个方法我用了很久比反复背API名称有效得多。最后说一句工程开发者的Java功底是你最大的优势而不是包袱。你对代码可读性、边界条件、异常处理的敏感度在竞赛里同样是加分项。别被性能差异吓到掌握了这些常用数据结构后Java在竞赛里足以支撑你拿下绝大多数题目。希望这份助记版能帮你少踩一些坑把时间花在解题思路上而不是和容器API较劲。