工程里真正用得上的十个算法套路
算法书里的问题会直接告诉你「求最长子串」，业务需求只会告诉你「统计每个用户最近连续签到多少天」。这篇按业务场景组织，每个套路配一个真实需求。
一、滑动窗口：一切「最近 N 秒/N 个」的问题
业务场景：接口限流，要求「每个用户每分钟最多 100 次请求」。
固定窗口计数有个经典缺陷：12:00:59 打 100 次、12:01:00 再打 100 次，两秒内实际放过了 200 次。滑动窗口能解决。
public class SlidingWindowLimiter {
private final int limit;
private final long windowMs;
// 每个用户一个队列，存放请求时间戳
private final Map<String, Deque<Long>> windows = new ConcurrentHashMap<>();
public boolean tryAcquire(String userId) {
long now = System.currentTimeMillis();
Deque<Long> q = windows.computeIfAbsent(userId, k -> new ArrayDeque<>());
synchronized (q) {
// 把滑出窗口的时间戳从队首移除
while (!q.isEmpty() && now - q.peekFirst() >= windowMs) {
q.pollFirst();
}
if (q.size() >= limit) {
return false;
}
q.offerLast(now);
return true;
}
}
}要点是队列里只保留窗口内的元素，每个时间戳最多入队一次、出队一次，均摊 O(1)。
单机版本用于演示，分布式场景用 Redis 的 ZSet 更实际——score 存时间戳，ZREMRANGEBYSCORE 清理过期，ZCARD 统计数量，整个操作放进一个 Lua 脚本保证原子性。
识别信号：需求里出现「最近」「连续」「每 N 秒内」，且答案随着窗口右边界移动而单调变化。
二、前缀和：把区间查询从 O(n) 降到 O(1)
业务场景：报表页要查「任意日期区间的订单总额」，用户会频繁切换时间范围。
每次查询都遍历区间内所有天，切一次时间范围就是一次全量累加。前缀和把它变成一次减法。
public class DailyAmountQuery {
private final long[] prefix; // prefix[i] = 第 0 到第 i-1 天的累计金额
private final LocalDate startDate;
public DailyAmountQuery(LocalDate startDate, long[] dailyAmount) {
this.startDate = startDate;
this.prefix = new long[dailyAmount.length + 1];
for (int i = 0; i < dailyAmount.length; i++) {
prefix[i + 1] = prefix[i] + dailyAmount[i];
}
}
/** 闭区间 [from, to] 的总额，O(1) */
public long sum(LocalDate from, LocalDate to) {
int l = (int) ChronoUnit.DAYS.between(startDate, from);
int r = (int) ChronoUnit.DAYS.between(startDate, to);
return prefix[r + 1] - prefix[l];
}
}在 SQL 里对应的就是把每日汇总物化成一张前缀和表。二维版本（前缀和矩阵）可以做「任意时间段 × 任意品类」的交叉查询。
识别信号：同一份不变的数据上要做大量区间聚合查询。数据频繁变动时改用树状数组或线段树。
三、二分答案：把「求最优解」变成「判断可行性」
业务场景：要把 100 万条数据分给 N 个线程处理，要求「最慢的那个线程尽可能快」。
直接求最优分配很难，但反过来问「限定每个线程最多处理 X 条，N 个线程够不够」就很简单。而这个可行性关于 X 是单调的——X 越大越容易满足。于是可以二分 X。
/** 把 chunks 分成不超过 threads 组，使「最大组的和」最小 */
public long minimizeMaxLoad(long[] chunks, int threads) {
long lo = Arrays.stream(chunks).max().orElse(0); // 下界：最大单块
long hi = Arrays.stream(chunks).sum(); // 上界：全给一个线程
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (feasible(chunks, threads, mid)) {
hi = mid; // 可行，尝试更小的上限
} else {
lo = mid + 1; // 不可行，上限必须更大
}
}
return lo;
}
/** 每组负载不超过 cap 时，能否分成 threads 组 */
private boolean feasible(long[] chunks, int threads, long cap) {
int groups = 1;
long cur = 0;
for (long c : chunks) {
if (cur + c > cap) {
groups++;
cur = c;
if (groups > threads) return false;
} else {
cur += c;
}
}
return true;
}同一个套路还能用来解决：「限流阈值设多少能保证 p99 不超过 200ms」「分片数取多少能让每片数据量不超过 500 万」。
识别信号：求「最大值最小化」或「最小值最大化」，且存在一个关于答案单调的判定函数。
四、堆：Top N 与「第 K 大」
业务场景：实时热搜榜，从每秒上万条搜索日志里取出 Top 100。
全量排序是 O(n log n) 且要把所有数据装进内存。用一个大小为 K 的小顶堆，只需 O(n log K) 和 O(K) 空间。
public List<Entry> topN(Iterator<Entry> stream, int k) {
// 小顶堆：堆顶是当前 Top K 里最小的那个
PriorityQueue<Entry> heap = new PriorityQueue<>(k, Comparator.comparingLong(Entry::count));
while (stream.hasNext()) {
Entry e = stream.next();
if (heap.size() < k) {
heap.offer(e);
} else if (e.count() > heap.peek().count()) {
heap.poll(); // 淘汰当前最小的
heap.offer(e);
}
}
List<Entry> result = new ArrayList<>(heap);
result.sort(Comparator.comparingLong(Entry::count).reversed());
return result;
}注意方向容易搞反：求 Top K 大用小顶堆，因为你需要快速知道「当前入选者里最弱的是谁」，好决定新来的能不能替换它。
海量数据下的分布式版本是「各分片各取 Top K，再归并取全局 Top K」。按记录的分数排名时，这样做是准确的；按 key 聚合计数（比如报名最多的城市）时，各分片的本地 Top K 合并后可能漏掉全局第一，Elasticsearch 聚合的精度问题就来自这里。同分规则、堆与快速选择的取舍和这两种情况的实测，见 只要前 100 名，为什么要把一百万条全排一遍。
识别信号：只要前 K 个，不需要全序；或者数据是流式的，装不进内存。
五、并查集：判断「是不是一伙的」
业务场景：风控要识别关联账号——共用过设备、共用过收货地址、有过转账关系的账号视为同一团伙。
关系是动态加入的，要频繁问「这两个账号是否同属一个团伙」。
public class UnionFind {
private final Map<String, String> parent = new HashMap<>();
private final Map<String, Integer> size = new HashMap<>();
public void add(String x) {
parent.putIfAbsent(x, x);
size.putIfAbsent(x, 1);
}
/** 路径压缩：查询时把路径上的节点直接挂到根上 */
public String find(String x) {
add(x);
String root = x;
while (!root.equals(parent.get(root))) {
root = parent.get(root);
}
while (!x.equals(root)) {
String next = parent.get(x);
parent.put(x, root);
x = next;
}
return root;
}
/** 按大小合并：小树挂到大树上，避免退化成链 */
public void union(String a, String b) {
String ra = find(a), rb = find(b);
if (ra.equals(rb)) return;
if (size.get(ra) < size.get(rb)) { String t = ra; ra = rb; rb = t; }
parent.put(rb, ra);
size.put(ra, size.get(ra) + size.get(rb));
}
public boolean connected(String a, String b) {
return find(a).equals(find(b));
}
public int groupSize(String x) {
return size.get(find(x));
}
}用法：
UnionFind uf = new UnionFind();
deviceShares.forEach(s -> uf.union(s.accountA(), s.accountB()));
transfers.forEach(t -> uf.union(t.from(), t.to()));
if (uf.groupSize(accountId) > 50) {
riskService.flag(accountId, "关联账号规模异常");
}路径压缩 + 按大小合并两个优化都加上后，均摊复杂度接近 O(1)。少了任何一个都可能退化。
识别信号：只关心「连通性」，不关心具体路径；关系只增不减。
六、拓扑排序：处理依赖顺序
业务场景：一个营销活动配置由多个规则组成，规则之间有依赖（「满减规则」依赖「商品范围规则」的计算结果），要确定执行顺序，并且要检测配置里有没有循环依赖。
/** 返回可执行顺序；存在循环依赖时抛异常，报出一条真实的环和受它阻塞的节点 */
public List<String> resolveOrder(Map<String, Set<String>> dependsOn) {
Map<String, Integer> inDegree = new HashMap<>();
Map<String, Set<String>> next = new HashMap<>();
for (var e : dependsOn.entrySet()) {
String node = e.getKey();
inDegree.putIfAbsent(node, 0);
for (String dep : e.getValue()) {
next.computeIfAbsent(dep, k -> new HashSet<>()).add(node);
inDegree.merge(node, 1, Integer::sum);
inDegree.putIfAbsent(dep, 0);
}
}
Deque<String> ready = inDegree.entrySet().stream()
.filter(e -> e.getValue() == 0)
.map(Map.Entry::getKey)
.collect(Collectors.toCollection(ArrayDeque::new));
List<String> order = new ArrayList<>();
while (!ready.isEmpty()) {
String cur = ready.poll();
order.add(cur);
for (String n : next.getOrDefault(cur, Set.of())) {
if (inDegree.merge(n, -1, Integer::sum) == 0) {
ready.offer(n);
}
}
}
if (order.size() != inDegree.size()) {
// 剩下的节点要么在环上，要么依赖了环上的节点，不能统称为「环上的节点」
Set<String> blocked = inDegree.entrySet().stream()
.filter(e -> e.getValue() > 0).map(Map.Entry::getKey)
.collect(Collectors.toCollection(TreeSet::new));
List<String> cycle = findCycle(blocked, dependsOn);
List<String> downstream = blocked.stream().filter(n -> !cycle.contains(n)).toList();
throw new IllegalStateException("循环依赖: " + String.join(" -> ", cycle) + "；受其阻塞: " + downstream);
}
return order;
}
/** 剩余节点都至少有一个依赖也在剩余集合里，沿依赖一直走，必然回到走过的节点 */
private List<String> findCycle(Set<String> blocked, Map<String, Set<String>> dependsOn) {
List<String> path = new ArrayList<>();
Map<String, Integer> seenAt = new HashMap<>();
String cur = blocked.iterator().next();
while (!seenAt.containsKey(cur)) {
seenAt.put(cur, path.size());
path.add(cur);
cur = dependsOn.get(cur).stream().filter(blocked::contains).sorted().findFirst().orElseThrow();
}
List<String> cycle = new ArrayList<>(path.subList(seenAt.get(cur), path.size()));
cycle.add(cur);
return cycle;
}Kahn 算法结束后剩下的节点，并不都在环上。「满减」依赖「范围」、「范围」又依赖「满减」，这是一个环；「会员折扣」只依赖「范围」，它不在环上，只是被环卡住了。如果把剩下的节点一股脑报成「环上的节点」，配置人员会去改一条本身没有问题的规则。上面的写法分开报告两类：从任一剩余节点出发沿依赖往回走，第一次走到重复节点时截出的那一段就是一条真实的环，其余是受它阻塞的节点。输入 A → B → A、C → B 时，异常信息是 循环依赖: A -> B -> A；受其阻塞: [C]。排好顺序之后，还要处理并发上限、失败传播和重试，见 依赖任务怎样安全地跑起来。
同样的结构还出现在 Maven 多模块项目的构建顺序、按外键确定建表顺序、ETL 任务调度里。Spring 容器处理 Bean 之间的依赖用的是按需递归创建，不是先排好序，循环依赖在那里有另一套表现，见 Spring 循环依赖。
识别信号：出现「A 必须在 B 之前」这类约束，且需要检测循环依赖。
七、单调栈：找「下一个更大/更小的元素」
业务场景：K 线图要标注「每个交易日之后，多少天内出现了更高的价格」。
暴力做法对每一天往后扫，O(n²)。单调栈一次遍历搞定。
/** 返回每天之后第一个价格更高的日子的间隔天数，没有则为 0 */
public int[] daysUntilHigher(int[] prices) {
int[] result = new int[prices.length];
Deque<Integer> stack = new ArrayDeque<>(); // 存下标，价格自栈底到栈顶递减
for (int i = 0; i < prices.length; i++) {
// 当前价格比栈顶高，说明栈顶等到了它的答案
while (!stack.isEmpty() && prices[i] > prices[stack.peek()]) {
int j = stack.pop();
result[j] = i - j;
}
stack.push(i);
}
// 栈里剩下的没有等到更高价，保持 0
return result;
}每个元素进栈一次、出栈一次，O(n)。同类问题还有「柱状图中最大矩形」（对应「一段时间内最长的、价格都不低于某值的区间」）。
识别信号：对每个元素求「左边/右边第一个满足某单调条件的元素」。
八、Trie：前缀匹配与敏感词
业务场景：搜索框输入联想，以及内容发布时的敏感词检测。
public class Trie {
private static class Node {
Map<Character, Node> children = new HashMap<>();
boolean end;
}
private final Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
cur = cur.children.computeIfAbsent(c, k -> new Node());
}
cur.end = true;
}
/** 返回文本中命中的所有敏感词位置，一次扫描 */
public List<int[]> findAll(String text) {
List<int[]> hits = new ArrayList<>();
for (int i = 0; i < text.length(); i++) {
Node cur = root;
for (int j = i; j < text.length(); j++) {
cur = cur.children.get(text.charAt(j));
if (cur == null) break;
if (cur.end) hits.add(new int[]{i, j});
}
}
return hits;
}
}上面这个实现是 O(n × m)（m 为最长词长度）。如果敏感词库很大且文本很长，应该升级到 AC 自动机——在 Trie 上加失配指针，把复杂度降到 O(n + 总词长)，本质是把 KMP 的思路搬到树上。
工程上还有两个必须处理的细节：变体绕过（「傻_逼」「s 逼」「傻B」）需要在匹配前做归一化——转小写、去除特殊字符、全角转半角、形近字映射；白名单要能覆盖误伤（「专业课」包含在某些词表里）。
识别信号：大量字符串的前缀匹配、多模式串同时匹配。
九、位运算：状态压缩与集合运算
业务场景：用户有 30 多种权限标签，要频繁做「是否拥有某权限」「取两个角色权限的交集」这类判断。
用 Set<String> 每次判断都要哈希计算，用 long 位图则是一条 CPU 指令。
public final class Permissions {
public static final long READ = 1L;
public static final long WRITE = 1L << 1;
public static final long DELETE = 1L << 2;
public static final long PUBLISH = 1L << 3;
public static final long AUDIT = 1L << 4;
/** 是否拥有全部指定权限 */
public static boolean hasAll(long held, long required) {
return (held & required) == required;
}
/** 是否拥有任一指定权限 */
public static boolean hasAny(long held, long required) {
return (held & required) != 0;
}
public static long grant(long held, long add) { return held | add; }
public static long revoke(long held, long remove){ return held & ~remove; }
public static long intersect(long a, long b) { return a & b; }
public static int count(long held) { return Long.bitCount(held); }
}其他高频用法：
// 判断奇偶，比取模快
boolean odd = (n & 1) == 1;
// 取最低位的 1，用于遍历位图里的每个置位
long lowest = n & (-n);
// 判断是否为 2 的幂（用于校验分片数、缓冲区大小配置）
boolean powerOfTwo = n > 0 && (n & (n - 1)) == 0;
// 取模优化：当 mod 是 2 的幂时，等价于按位与
int slot = hash & (capacity - 1); // HashMap 定位桶用的就是这个注意上限：long 只有 64 位。超过 64 种标签要用 BitSet 或者多个 long。
识别信号：状态是有限个布尔标记的组合；需要高频做集合的交并差。
十、快慢指针与对顶堆：环检测与流式中位数
业务场景一：检测配置引用链是否成环（A 引用 B，B 引用 C，C 又引用 A），且不想额外分配一个 Set 来存访问记录。
public boolean hasCycle(String start, Function<String, String> nextRef) {
String slow = start, fast = start;
while (fast != null && nextRef.apply(fast) != null) {
slow = nextRef.apply(slow);
fast = nextRef.apply(nextRef.apply(fast));
if (slow != null && slow.equals(fast)) {
return true;
}
}
return false;
}业务场景二：流式数据上随时取中位数，比如一场活动里所有已提交出价的中位数。用两个堆（对顶堆）维护「较小的一半」和「较大的一半」：
public class StreamingMedian {
private final PriorityQueue<Long> lower = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶
private final PriorityQueue<Long> upper = new PriorityQueue<>(); // 小顶
public void add(long v) {
lower.offer(v);
upper.offer(lower.poll()); // 先过一遍 lower，保证 lower 的元素都 <= upper
if (upper.size() > lower.size()) {
lower.offer(upper.poll()); // 保持 lower.size() >= upper.size()
}
}
public double median() {
if (lower.isEmpty()) return 0;
return lower.size() > upper.size()
? lower.peek()
: (lower.peek() + upper.peek()) / 2.0;
}
}识别信号：链式结构上的环检测；需要在流式数据上维护「中间位置」。
对顶堆要保存全部样本，内存随数据量增长，多个实例各自算出的中位数也没法合并。所以它不适合做接口延迟监控：监控要的是 p50、p99 能跨实例聚合，做法是上报直方图、在查询端计算分位数，见 可观测性 中「关于分位数的一个坑」。
怎么在业务里认出这些套路
难点从来不是记住算法，而是从需求描述里认出它。几个可复用的翻译规则：
| 需求里的说法 | 大概率是 |
|---|---|
| 最近 N 分钟内 / 连续 | 滑动窗口 |
| 任意时间段的总和/平均 | 前缀和 |
| 尽可能均匀地分配 / 最大值最小 | 二分答案 |
| 排行榜 / 热门前 N | 堆 |
| 关联账号 / 是否同一批 | 并查集 |
| 依赖顺序 / 循环依赖检测 | 拓扑排序 |
| 下一个更高的 / 左边第一个更小的 | 单调栈 |
| 输入联想 / 敏感词 | Trie（词库大就上 AC 自动机） |
| 一堆开关状态的组合判断 | 位运算 |
| 引用成环 / 流式数据的中位数 | 快慢指针、对顶堆 |
最后提醒一句：绝大多数业务代码不需要算法，HashMap 加一次遍历就够了。上面这些套路的价值在于——当数据量真的上来、简单写法真的扛不住时，你知道往哪个方向改。提前套用只会增加复杂度。