1. 工程思维与竞赛思维的第一个分岔口容器选择1.1 先记住一条铁律能数组就数组ArrayList 是保底方案我做Java后端快十年日常业务代码里 ArrayList 顺手就用泛型、迭代器、流式操作都挺舒服。但第一次认真刷算法题时我连续卡在几个不该卡的地方——不是不会算法是容器选错了。后来我把代码换成数组时间直接腰斩。先说结论在算法竞赛里“ArrayList 能用”和“ArrayList 适合用”是两回事。原因在源码层面就能看出来。ArrayList.get(i) 要越界检查add 时可能触发扩容扩容本质是 Arrays.copyOf 底层调用 System.arraycopy 再整体搬迁。更麻烦的是 ArrayList 里的每个元素都是包装类型你拿来和 int 做运算处处是拆箱装箱。算法题的数据量动不动是 10^5、10^6这些操作会被循环放大成肉眼可见的时间差。所以我的习惯是只要数组长度在输入时就确定了一律用原生数组。int[] arr、long[] pre、char[] ch能不用集合就不用集合。// 工程习惯谁先谁后都很自由的动态列表 ListInteger list new ArrayList(); for (int i 0; i n; i) list.add(sc.nextInt()); // 竞赛习惯输入第一行就是 n直接开固定数组 int[] arr new int[n]; for (int i 0; i n; i) arr[i] sc.nextInt();1.2 LinkedList 在竞赛里基本可以告别舞台很多工程开发者对 LinkedList 有蜜汁好感因为它“插入删除都是 O(1)”。但如果只是插入删除 O(1)、随机访问 O(n)在算法竞赛里几乎没有任何优势。你需要头部弹出、尾部追加的场景ArrayDeque 全覆盖你需要按索引访问的场景LinkedList 会拖到你想哭。还有一个隐蔽的坑LinkedList 每个节点是独立对象分布在堆里访问不连续。在大量操作的循环里它对 CPU 缓存不友好比数组结构慢得多。竞赛数据量一大这种慢会被放大。我见过有人用 LinkedList 存图顶点做 BFS每次 get 邻居列表都从链表头开始遍历……这种代码在本地跑着没感觉一上 OJ 就超时。LinkedList 唯一说得过去的场景是你要一个并发环境下已经加了同步包装的队列——但这在竞赛里根本不存在因为竞赛本身就是单线程。1.3 二维数组与邻接表图论题的容器选型图论题里邻接矩阵和邻接表的取舍是每个工程开发者都要重新学一遍的。工程上写邻接表大家默认 ListList graph new ArrayList()用起来舒服。竞赛里这个写法不是不行但更推荐数组嵌套。// 常见竞赛写法邻接表 ListInteger[] graph new ArrayList[n]; for (int i 0; i n; i) graph[i] new ArrayList(); graph[u].add(v); // 稠密图或 n 很小直接用矩阵 int[][] g new int[n][n]; g[u][v] 1;判断标准很简单如果 n 不超过 1000、而且需要频繁判断“u 到 v 是否有边”邻接矩阵 O(1) 查询很香如果 n 到 10^5、边数是稀疏的必须邻接表否则内存先爆给你看。邻接矩阵 int[n][n] 要小心内存n 5000 时 2500 万个 int约 100MB很多 OJ 内存上限就 256MB够呛n 10000 时 4 亿个 int约 1.6GB直接 MEMORY_LIMIT_EXCEEDED。1.4 预分配容量让你的动态结构别在半路扩容就算非用 ArrayList 不可也请给初始容量。默认容量是 10一个 10^5 规模的数据会让 ArrayList 扩容很多次每次扩容都伴随一次 O(n) 的数组复制。// 差不知道会 add 多少次 ListInteger list new ArrayList(); // 好已知上界一步到位 ListInteger list new ArrayList(n);HashMap 同理。工程代码里不在意 HashMap 默认容量因为负载因子 0.75、扩容阈值这些都会自适应。但竞赛里你如果能预估元素个数new HashMap(n * 2) 能减少扩容带来的 rehash 开销。这条经验特别适合从工程转竞赛的人工程里我们把“动态扩容”当优点竞赛里我们要把它当成“已知成本”提前消灭。2. 数组与字符串竞赛里最容易被“高级写法”拖慢的地方2.1 Arrays.sort 的两种底层实现决定你要不要担心排序稳定性很多工程同事不知道Arrays.sort 对基本类型数组和对象数组用了完全不同的排序算法。对 int[]、long[] 等基本类型数组DualPivotQuicksort不稳定。对 Integer[]、String[] 等对象数组TimSort稳定。这点在算法题里非常关键。比如一个二维点数组你要按 x 排序x 相同时保持 y 的顺序。如果直接对 Point 对象数组排序TimSort 稳定没问题如果你把坐标拆成两个平行数组又或者用基本类型数组做键排序那就没稳定性了。一个通用方案是包装下标数组Integer[] idx new Integer[n]; for (int i 0; i n; i) idx[i] i; Arrays.sort(idx, (a, b) - Integer.compare(arr[a], arr[b]));比较器里永远用 Integer.compare而不是 arr[a] - arr[b]。后者看着简单但 arr 是 long 时差值可能溢出 int排序结果直接错乱。我用一次 long 数组排序踩过这个坑输出结果诡异了半天最后才发现是减法溢出。2.2 char[] 与 StringBuilder什么时候用哪个一句话讲清楚字符串题是工程开发者的重灾区因为我们太习惯 String 的各种 API 了。需要频繁修改字符串中的字符就转成 char[]需要反复拼接就用 StringBuilder。两者不要拧着来。// 反转一个字符串 // 工程写法 String reversed new StringBuilder(s).reverse().toString(); // 竞赛写法双指针交换 char[] char[] cs s.toCharArray(); int l 0, r cs.length - 1; while (l r) { char t cs[l]; cs[l] cs[r]; cs[r--] t; }不是说工程写法不能 AC而是竞赛里场景多样。比如你要判断回文串、要原地修改、要比较旋转后的字符串char[] 明显更适合。charAt(i) 在 JIT 足够热的时候不慢但你没法通过 charAt 修改字符——String 是不可变的。还有一点必须提醒不要用 拼字符串。每次 都会创建一个新 String 对象循环拼 N 次复杂度 O(n^2)数据一大必超时。要用 StringBuilder 就用到底中途切回 String 再拼等于白做。2.3 split 是个隐蔽的性能黑洞手写解析更稳String.split 的参数是正则表达式不是普通字符。我见过无数人在按逗号分割时写成 s.split(,) 然后奇怪为什么结果不对——实际没问题但按点号分割必须写 s.split(\.)因为点号在正则里匹配任意字符。更隐患的是性能split 每次都会编译正则如果你在循环里对大量字符串调用 split开销很可观。竞赛里常见的输入解析我一般这样处理BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());如果只有一行数直接用 split( ) 完全够用如果数据量大、需要反复多次解析手写一个按空格和换行分割的 fast reader 反而更稳。实在不想手写可以用 StreamTokenizer但它的 API 比较怪我建议直接用 StringTokenizer 就好。2.4 转换类操作进制、求值、比较的边界条件Integer.parseInt 有两个参数版本第二个是 radix。很多工程开发者不知道这个参数遇到十六进制转换只能手写循环。int val Integer.parseInt(ff, 16); // 255 String hex Integer.toString(255, 16); // ff但要注意Integer.parseInt 遇到超出 int 范围的值会抛 NumberFormatException。竞赛里经常要处理比 long 还大的数这时候要么用 BigInteger要么干脆按字符串处理。BigInteger 的加减乘除都能用但千万别在循环里用 BigInteger 做乘法速度慢到怀疑人生。进制转换还有一个隐蔽问题负数。Integer.toString(-1, 2) 结果是 11111111111111111111111111111111这是补码表示不是简单去掉符号位。如果题目要的是标准的二进制位表示可能得自己处理。3. 栈、队列与双端队列先分清 Deque 再谈优化3.1 Stack 类为什么不该用不是因为它错是因为它有锁很多 Java 教程和面试八股里还在用 Stack但仔细看过源码你就知道Stack 继承自 Vector所有公开方法都带 synchronized。单线程环境下这个锁不会造成数据竞争但会带来不必要的同步开销。竞赛里栈的标准替代是 ArrayDequeDequeInteger stack new ArrayDeque(); stack.push(1); stack.pop(); stack.peek();有同行跟我说工程上并发环境可能需要同步集合Stack 在某些遗留代码里还有存在价值。这个我不否认但算法竞赛里绝对不该出现 Stack选 ArrayDeque 就完事了。3.2 ArrayDeque 方法名对照表别再 offer 和 push 混用ArrayDeque 的 API 是出了名的多因为它同时实现了 Deque 双端队列接口。同一个操作有完全不同的叫法连工作多年的工程师都会弄混。操作语义队列视角栈视角双端视角尾部入队offer(e)-addLast(e)头部出队poll()-removeFirst()头部入栈-push(e)addFirst(e)头部出栈-pop()removeFirst()查看头部peek()peek()getFirst()查看尾部--peekLast()表格之外的坑用 offer 加、用 pop 取也能跑因为 push 和 pop 操作的是同一端。但这样代码语义混乱别人看你代码容易误解。建议一个容器只认准一个视角当队列用就只用 offer/poll/peek当栈用就只用 push/pop/peek。ArrayDeque 底层是循环数组初始容量 16。大量元素时它会自动扩容但扩容也是复制数组所以大数组场景尽量预估容量new ArrayDeque(n) 直接指定。3.3 单调队列套路存下标不存值这是竞赛专属的容器用法滑动窗口最大值是一道经典题工程里你可能用优先队列或者直接扫描竞赛里标准解法是单调队列。int[] nums ...; int k 3; DequeInteger q new ArrayDeque(); for (int i 0; i n; i) { // 把队尾所有小于当前值的下标弹出去 while (!q.isEmpty() nums[q.peekLast()] nums[i]) { q.pollLast(); } q.offerLast(i); // 把窗口外的下标弹出 while (!q.isEmpty() q.peekFirst() i - k) { q.pollFirst(); } if (i k - 1) { // 队头就是当前窗口最大值 res[i - k 1] nums[q.peekFirst()]; } }核心技巧队列里存的是下标而不是值。为什么要存下标因为你要判断这个元素是否已经滑出窗口。只存值的话还得额外开一个数组记录位置或者用 pair 结构平白多一层封装。这里要特别注意方法名pollLast 操作队尾、peekFirst 查看队头跟我日常 BFS 用的 poll() 不太一样。我第一次写单调队列时把 peekFirst 写成了 peek结果每次都在比较队头旧元素逻辑直接乱套。3.4 BFS 的队列、DFS 的栈以及递归爆栈问题BFS 题目标准容器就是 ArrayDeque这个没什么可说的模板背下来DequeInteger q new ArrayDeque(); q.offer(start); while (!q.isEmpty()) { int u q.poll(); for (int v : graph[u]) { if (!visited[v]) { visited[v] true; q.offer(v); } } }DFS 一般直接递归但 Java 默认栈大小有限递归深度超过几千层就可能 StackOverflowError。OJ 里你不能随意修改 -Xss 参数所以深度极大的 DFS 要么改用显式栈迭代要么改 BFS。显式栈迭代时用 ArrayDeque 模拟栈遍历顺序会跟递归略有不同注意标记 visited 的时机。递归是进入时就标记迭代可以在弹出时才标记两种写法的去重后果不一样竞赛里这是个经典细节。4. PriorityQueue最被高估也最容易用错的容器4.1 默认是小根堆大根堆要用比较器PriorityQueue 默认是最小堆poll 出来的是最小值。但堆顶元素小只是它的习惯。很多工程开发者第一次用 PriorityQueue 找最大元素直接 add 完就开始 poll结果输出一串最小的数一脸疑惑。大根堆的标准写法PriorityQueueInteger maxHeap new PriorityQueue(Collections.reverseOrder()); // 或者自定义比较器 PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a);这里要提醒b - a 这种写法虽然能过但不推荐原因跟之前一样数值极值会溢出。正规范式是 (b, a) - Integer.compare(b, a) 或者 Comparator.reverseOrder()。如果堆里存的是 int[]、long[] 这种数组比较器要按数组的某个维度写// 按数组第 1 个元素从小到大 PriorityQueueint[] pq new PriorityQueue((a, b) - Integer.compare(a[1], b[1]));4.2 三个真实翻车现场修改堆内元素、遍历顺序、比较器方向先说前两个因为都跟“堆”的数据结构性质有关。堆只保证堆顶元素在全局最优不保证整个数据集合有序。所以不要在拿到 PriorityQueue 之后用迭代器遍历并期望它是升序的。我见过有同事为了拿有序集合new 一个 PriorityQueue然后 for (int x : pq) 遍历结果顺序乱得一批。想拿有序数据就用 Arrays.sort 或 TreeSet。第二个坑是修改堆内元素。PriorityQueue 不提供更新优先级的 API。你如果把一个对象放进堆里然后修改了它参与比较的字段堆的性质就被破坏了。pq.add(node); node.val 10; // 堆序已经失效 // 正确做法先删再加 pq.remove(node); node.val 10; pq.add(node);这个坑在 Dijkstra 里尤其经典。很多人实现 Dijkstra 时建一个 distance 数组然后修改 distance 后想当然地以为 PriorityQueue 会重新排序。正确做法要么是 remove 再 offer要么干脆往堆里塞 (新的距离, 节点编号)每次弹出时检查这个距离是不是过期的。比较器方向写反是第三个坑也是最隐蔽的。比如你要找前 k 个最大元素很自然会写 maxHeap 然后每次 poll 最小的但堆的容量固定 k 时你要 poll 的恰恰是“当前最小”写起来方向容易拧。提交完之后发现结果反了再回去找比较器费时费力。我现在的习惯是写完比较器先跑一组极值数据比如 [1, 100, 999]确定方向对了再继续。4.3 很多场景根本不需要堆排序 双指针就够工程里的“TopK 问题”通常直接用 PriorityQueue因为数据可能源源不断。但竞赛里的 K 和 n 都是给出范围的很多时候 Arrays.sort 一把梭就结束了。比如 n 10^5要第 K 大的数。排序 O(n log n) 稳过何必再维护一个大小为 K 的堆。只有数据量逼近 10^6 而且只找 TopK 时堆的 O(n log k) 才显示出优势。更多时候先排序再取下标代码简单而且不容易写错。要注意的是Java 的 Arrays.sort 对基本类型数组的常数非常小JIT 后性能很好。相比之下PriorityQueue 的泛型和比较器会让常数变大。在竞赛里O(n log n) 的排序往往比 O(n log k) 的堆更快因为它省掉了对象创建和比较器调用的开销。4.4 动态有序集合选 TreeMap/TreeSet而不是堆堆的另一个弱点是你无法访问堆里除了堆顶之外的其他元素无法定位某个元素的前驱后继。竞赛里经常有这种题维护一个有序集合支持插入、删除、查询前驱后继。标准答案是 TreeSet 和 TreeMap它们基于红黑树所有操作都是 O(log n)。TreeSetInteger set new TreeSet(); set.add(1); set.add(7); set.ceiling(5); // 返回 5 的最小元素7 set.floor(5); // 返回 5 的最大元素1 set.higher(5); // 返回 5 的最小元素7 set.lower(5); // 返回 5 的最小元素1这四个方法名特别容易混。我记的方法是ceiling天花板是往上够floor地板是往下找higher/lower 则是严格大于/严格小于。ceiling 和 floor 允许等于higher 和 lower 不允许等于。这里要注意 TreeMap 的键必须是可比较的要么实现了 Comparable要么构造时传入 Comparator。竞赛里如果键是二维坐标建议组合成 Long 而不是用自定义对象理由在下一章讲。5. 哈希与有序键值HashMap 之外你还需要知道的5.1 统计频率别用 MapCharacter, Integer用定长数组这是我从工程转竞赛时最大的习惯冲击。业务代码里统计频率我第一反应是MapCharacter, Integer freq new HashMap(); freq.put(c, freq.getOrDefault(c, 0) 1);但竞赛里如果字符集已知比如小写字母 26 个、ASCII 256 个直接开数组int[] freq new int[26]; freq[c - a];这不仅仅是代码更短性能也更好。HashMap 的 get/put 背后是哈希计算、桶定位、链表或红黑树遍历而数组访问就是一次内存寻址。在统计 10^6 个字符时这个差距是数量级的。判定标准如下键的取值范围有限且稀疏度可控用数组取值范围大或高度稀疏用 HashMap。比如统计长整数数组里每个数出现次数值域太大只能 HashMap。5.2 int[] 不能直接当 HashMap 的 Key数组的 equals 是按引用的这是几乎每个 Java 开发者都会踩的坑。HashMapint[], Boolean 里两个内容相同的 int[] 是不同 Key因为数组没有重写 equals默认使用 Object 的引用比较。我见过有人用 int[]{x, y} 作为坐标 Key 存图结果怎么查都查不到一度怀疑 HashMap 坏了。解决方案有几个// 方案1组合成 Long最快 long key ((long) x 32) | (y 0xffffffffL); // 方案2组合成 String直观但慢 String key x , y; // 方案3转成 ListIntegerequals 内容比较但可变有风险 ListInteger key Arrays.asList(x, y);我的建议是能组合就组合。二维坐标转 Long 是竞赛里最常见的写法不仅避免 Key 可变问题还省掉大量对象开销。不过要注意位移运算的细节y 是负数时直接 | y 会把高位弄脏所以 上 0xffffffffL 或者用 Integer.toUnsignedLong(y) 都行。这种边界题做多了自然就记住了。5.3 TreeMap 的边界方法适合动态范围查询TreeMap 除了上一章说的 ceiling/floor 系列还有两个很方便的方法firstKey() 和 lastKey()取最小和最大键。这在维护区间最小值、最大值时很实用。比如经典的合并区间题你需要维护一堆区间左端点快速找到最小左端点所在的区间。TreeMapInteger, Integer 天然合适。一个隐蔽点firstKey() 的复杂度是 O(log n)不是 O(1)因为它要从根节点一路往左走。工程里你可能经常调用 firstKey()注意别把它放进高频循环里。如果你需要按插入顺序遍历用 LinkedHashMap。它在 HashMap 基础上维护了一个双向链表遍历顺序和插入顺序一致。但竞赛里 LinkedHashMap 用得少因为题目很少需要“保持插入序”的 Map工程里做 LRU 缓存才常用到它的 accessOrder 属性。5.4 手写简易哈希表什么时候标准库会成为瓶颈HashMap 在绝大多数场景都够用但极端情况下确实会卡常数。比如你需要做 10^7 次 put/get每次都是泛型对象、哈希计算、可能还有扩容时间可能逼近极限。竞赛选手偶尔会手写一个超简单的哈希表用数组模拟拉链int mod 1000003; int[] head new int[mod]; int[] next new int[MAX]; long[] key new long[MAX]; int[] val new int[MAX]; int cnt 0; void put(long k, int v) { int h (int) ((k % mod mod) % mod); for (int i head[h]; i ! -1; i next[i]) { if (key[i] k) { val[i] v; return; } } key[cnt] k; val[cnt] v; next[cnt] head[h]; head[h] cnt; }这个东西的好处是快坏处是容易写错而且一旦冲突太多会退化。我建议只有当 HashMap 成了可观测的性能瓶颈时再手写否则纯属给自己找麻烦。6. 助记速查表高频操作的“一句话答案”6.1 场景到容器的快速决策表下表基本覆盖了我在算法竞赛里最常用的容器选择与操作适合打印出来贴显示器旁边。场景首选容器/工具关键操作注意点固定长度数组int[] / long[]arr[i]性能优于 ArrayList动态变长列表ArrayListadd/get记得预估容量队列FIFOArrayDequeoffer/poll/peek别用 LinkedList栈LIFOArrayDequepush/pop/peek别用 Stack滑动窗口最值ArrayDequepollLast/offerLast/peekFirst存下标别存值TopK 动态PriorityQueueoffer/poll写对比较器方向有序动态集合TreeSetceiling/floor/higher/lower键要可比较有序键值TreeMapK,VfirstKey/lastKey/ceilingKey复杂度 O(log n)频率统计值域小int[]arr[x]比 HashMap 快得多频率统计值域大HashMapK,Vmerge/getOrDefault注意扩容开销二维坐标 KeyLong组合位移数组不能直接做 Key6.2 高概率会写错的 API 清单这部分是我自己踩过坑后整理出来的每一条都对应一个真实的调试血泪史PriorityQueue 默认是小根堆要最大值必须 reverseOrder 或自定义比较器。Arrays.sort 对 int[] 不稳定需要稳定排序时用对象数组和 TimSort。StringBuilder.reverse 返回新对象别指望它原地修改并沿用原引用。ArrayDeque 不允许 null 元素offer(null) 会抛 NPE。HashMap 的 key 如果是可变对象修改后查找会失效。Stack 的 search 是找下标不是判断存在性而且方法带锁。substring 在 Java 7 之后是 O(n) 复制不是 O(1) 视图。list.remove(int) 删除的是下标list.remove(Object) 删除的是元素类型传错就是另一段故事。最后一条特别常见ArrayList 里你想删除数字 3写了 list.remove(3)结果删的是下标 3 的元素。要删对象必须传 Integer.valueOf(3)。这种错误在竞赛里一出现就是 WA 一片。6.3 写算法题时我自己的容器检查清单下面是我每次提交前会快速过一遍的检查习惯分享给大家第一看题目给的数据范围。n 小于 10^5 时普通 HashMap 和 ArrayList 一般没问题n 到 10^6 甚至更大优先考虑数组、预分配容量、基本类型。第二看清楚容器方法的返回值。poll 在队列为空时返回 null但 remove 会抛异常get 越界会抛异常但 Stream 操作会返回 Optional。竞赛里没人帮你 try-catch写之前就要想清楚边界。第三比较器方向永远值得复查一遍。写逆序比较器时跑一个最小样例验证输出顺序写 Diijkstra 的距离堆时检查是不是每个节点可能多次入堆需要配合 visited 或距离判断跳过过期记录。第四注意 OJ 的 Java 版本。有些 OJ 还停留在旧版本lambda、var、甚至 List.of 都可能不支持。提交前确认语法兼容性免得因为编译问题白白罚时。第五递归深度超过一万层的题先怀疑自己该用迭代而不是递归。Java 默认线程栈在 Linux 上通常是 1MB简单递归到几千层就可能溢出了。真遇到阵列爆炸检查是不是写成了死递归再考虑换显式栈。这份清单不是一天形成的而是被多次 Time Limit Exceeded 和 Wrong Answer 喂出来的。每次多检查一条就能少一次返工。tool▁c▁38