面试真题与回答讲解 第 51 页，共 52 页
浏览 OfferCC 面试真题与回答讲解第 51 页，查看解题思路、实现细节、追问和公开来源。
算法面试题：寻找数组中的第 K 大元素
从完整排序和固定大小堆推导到随机化三向快速选择，讲清分区不变量、重复值处理、复杂度权衡，并用可执行测试验证实现。
算法面试：复制带随机指针的链表
从节点身份映射推导带随机指针链表的深拷贝，再掌握交织节点的常数辅助空间优化、正确性不变量和原链表恢复方法。
算法面试：如何找出网络中的所有关键连接？
用发现时间和 low-link 值在线性时间内找出无向图的全部桥，并证明严格判定条件，给出不受递归深度限制的迭代 DFS 实现。
算法面试：如何 K 个一组反转链表？
用哑节点、完整分组预检和区间内指针反转解决 K 个一组反转链表，并用循环不变量证明尾部不足 K 个节点时保持原序。
算法面试：如何求柱状图中的最大矩形？
从左右第一个更矮柱推导柱状图最大矩形算法，实现单次扫描的单调栈，并证明正确性与线性复杂度。
算法面试：如何用动态规划计算编辑距离？
从字符串前缀推导编辑距离递推式，证明三种状态转移，并用 TypeScript 滚动数组实现 O(mn) 时间、O(min(m, n)) 空间的解法。
算法面试：如何用二分查找求最长递增子序列？
从 O(n²) 动态规划推导最小尾值不变量，再用二分查找、前驱索引和属性测试实现并证明 O(n log n) 的最长递增子序列算法。
算法面试：如何用双向 BFS 解单词接龙？
把单词接龙建模为隐式无权图，从最短序列要求推导 BFS，并实现始终扩展较小前沿的双向搜索，给出严谨证明、复杂度核算与对抗测试。
算法面试：如何实现 O(1) 的 LFU 缓存？
用键索引、频次桶、桶内双向链表和最小频次指针实现 LFU 缓存，处理同频 LRU 淘汰，并证明 get 与 put 的期望 O(1) 复杂度。
算法面试：如何求最小覆盖子串？
从二次枚举推导可变长滑动窗口，用需求频次、满足种类数和收缩不变量在线找到最短覆盖区间，并通过重复字符、无解输入和随机差分验证 TypeScript 实现。
算法面试：如何用双指针解决接雨水？
从逐列蓄水公式推导前后缀数组与双指针方案，用边界不变量证明为什么能安全移动较小一侧，并以 O(n) 时间、O(1) 额外空间实现和验证。
算法面试：如何合并 K 个有序链表？
从候选头节点不变量推导 O(N log k) 解法，用大小不超过 k 的最小堆完成实现与正确性证明，并比较扫描、顺序合并、排序和分治方案。
算法面试：如何实现 Dijkstra 最短路径算法？
用邻接表、最小堆惰性删除与前驱数组实现 Dijkstra，并证明贪心不变量，讲清提前退出、复杂度和负权边界。
算法面试：如何实现并查集并维护连通分量？
从动态连通查询推导并查集，用按大小合并和路径折半实现 union、connected 与分量计数，并解释正确性、均摊复杂度、测试方法和删除边界。
算法面试：如何用单调队列求滑动窗口最大值？
从暴力扫描和堆方案推导单调双端队列，用支配关系、不变量与摊还分析证明 O(n) 时间，并给出实际只占 O(k) 空间的 TypeScript 环形队列实现。
算法面试：如何求二叉树的最近公共祖先？
从路径方案推导一次后序遍历，用子树返回值不变量证明最近公共祖先算法，并处理重复值、缺失节点、极深树和多次查询等常见追问。
算法面试：如何序列化和反序列化二叉树？
用带空节点标记的前序遍历设计可逆编码，证明解码器如何恰好消费一棵子树，并处理非法输入、深树边界与替代格式。
算法面试：如何求数据流的动态中位数？
用最大堆维护较小的一半、最小堆维护较大的一半，从不变量推导 O(log n) 插入和 O(1) 查询，并覆盖边界、正确性证明与滑动窗口追问。
算法面试：如何用二分查找目标值的首尾位置？
用 lower bound 与 upper bound 统一处理重复值、空数组和目标不存在的情况，并通过半开区间不变量证明 O(log n) 解法正确。
算法面试：如何合并重叠区间？
用排序加贪心扫描合并重叠闭区间，解释端点语义、正确性不变量、复杂度与输入不可变，并覆盖嵌套、链式重叠和流式处理等追问。
如何用拓扑排序解决课程表 II？
从课程依赖关系推导 Kahn 拓扑排序，解释建图方向、零入度不变量、环检测证明，并处理多解、重复边和并行学期等追问。
如何实现支持插入、查找、前缀匹配和删除的 Trie？
从精确查找和前缀匹配需求推导 Trie，实现不会破坏共享路径的安全删除，并验证终止标记不变量、复杂度和对抗用例。
如何设计动态 Top-K 高频元素数据结构？
从读写比例推导动态 Top-K 的精确数据结构，给出可运行的频次桶实现、正确性不变量与复杂度，并说明内存受限时何时改用 Space-Saving 或 Count-Min Sketch。
如何实现线程安全的有界阻塞队列？
用环形数组、互斥锁和两个条件变量实现有界阻塞队列，并从状态不变量、线性化点、虚假唤醒和中断语义证明多生产者、多消费者下的正确性。