马士兵教育 |MCA算法高频题目讲解

算法面试里最让人难受的场景，不是题没见过，而是题看着眼熟、也写过类似代码，面试官换个问法就卡住了。MCA 这类题目之所以被反复拿出来考，不是因为它们有多偏，而是因为它们卡在能力缺口上：会写链表反转，不等于能在资源限制下做出取舍；能背出快排，不等于能从题目里挖出单调性。

这份《马士兵教育 | MCA算法高频题目讲解》适合用来做一次针对性的查漏补缺，而不是当成又一轮从头刷题的起点。下面按几类典型缺口拆开讲，你可以对照自己的情况决定从哪一节切入。

缺口一：基本数据结构只是「知道」，不是「能用」

很多人对数组、链表、栈、队列、哈希表、堆、树的定义说得出来，但一到实际题目里就不知道该挑哪个。比如同样是维护一个窗口内的极值，用堆和用双端队列的代价差在哪里；同样是去重，哈希表和排序后处理各自在什么约束下更划算。这类判断力不是靠背结构定义练出来的，而是靠反复在题目里做选择练出来的。

如果你属于「结构都认识，但拿到题第一反应是枚举暴力解」的状态，这部分要优先补。建议的练习方式：每读完一道题，先不写代码，只在纸上写出候选结构、各自的时间与空间代价、以及你最终选它的理由。这个动作比直接敲代码更锻炼判断。

缺口二：题面里那点「单调性」，你看不出来

单调性是面试里区分度很高的一类考点。题目不会直接告诉你「这里可以用单调栈」，而是把条件藏在数据的排列方式、答案的取值范围或者操作的先后顺序里。能不能把它挖出来，往往决定了你是写出 O(n²) 还是 O(n)。

补齐这块的关键不是记模板，而是练「从条件里找序」的习惯。看到「下一个更大的」「左边第一个小于的」「区间最值」这类描述，先问自己：这里存在一个随着下标推进而单调变化的量吗？把这个问题问成条件反射，模板才有地方可用。

缺口三：资源限制类题目没有系统方法

「内存只有 1G，文件有 100G，怎么排序」「只能用常数级额外空间」——这类题卡住的人特别多，因为平时刷题几乎不关心内存和外部存储。其实它有一整套固定的思路来源：分块、外排、位图、布隆过滤、多轮扫描、哈希分桶。每一种都对应特定的约束组合。

建议把这类题单独拉出来做一个小专题，每做一道就记下「限制条件是什么、用了哪种手段、为什么别的手段在这里行不通」。积累十道左右，你面对新题时就有牌可打了。

缺口四：把算法能力和数学能力绑在一起

不少人一看到复杂度推导、概率期望、位运算就退缩，觉得自己数学底子不行，算法也就学不动。实际上日常面试考察的数学成分相当有限，绝大多数题目要的是清晰的逻辑推导和边界处理，不是竞赛级别的数论功底。真正需要补的是：会用渐近记号描述代价、会做简单的期望分析、熟悉二进制与位运算的常见技巧。这三样都能在短期内补上，不需要重学高数。

学完之后，你应该能回答这些问题

• 面对一道新题，你能在几分钟内说出候选数据结构和取舍理由吗？
• 看到「区间」「下一个更大」「滑动窗口」，你能立刻判断该不该往单调性上想吗？
• 遇到内存或数据量受限的题目，你能列出至少三种可选手段并说明适用条件吗？
• 你能不能用渐近记号准确描述自己解法的代价，而不是含糊地说「挺快的」？

如果上面有几条你答得含糊，那就说明对应的缺口还在。建议按缺口的顺序挑着看，而不是一集不落地从头刷到尾——查漏补缺的效率，取决于你愿不愿意先承认自己缺在哪。