LeetCode双周赛T3分水岭：有序集合模型识别与O(n log n)优化-北京尧图网络

双周赛做到T3这个位置基本就是一场比赛的分水岭。前两题考的是手速和基础功T3开始才是真正拉开差距的地方。LeetCode双周赛的第三题往往卡在“思路能想到但写起来容易翻车”的尴尬位置尤其是174场双周赛这道T3赛后群里讨论热度不低不少人卡在超时上也有人栽在边界条件里。这篇文章把我对这道题的拆解、赛时的思考路径、以及赛后补题时的代码实现完整梳理一遍给同样卡过这道题的朋友一个参考。1. 先理解双周赛T3的定位与难点1.1 双周赛题目难度梯度分析做过几场双周赛的朋友应该能明显感觉到题目的难度分布是有规律的。T1基本是签到题考的是最基本的循环、判断、字符串处理大概5到8分钟就能ACT2开始加入一些简单的数据结构和算法思想比如哈希表计数、双指针、贪心难度在中等偏下而T3就是分水岭它的定位是“中等偏上”到“困难之间”的过渡地带。到了T4那就是不折不扣的压轴难题了。为什么T3这么重要因为它直接决定了你是稳坐三题选手还是两题选手。在双周赛的排名体系里做出T3和做不出T3名次往往能差出几百名甚至上千名。174场双周赛的T3尤其典型它考的不是什么冷门算法而是你平时刷题时经常见到的数据结构但换了个包装方式很多人就认不出来了。1.2 为什么这道题会成为“卡人”的分水岭我从赛后交流群里收集到的反馈来看大家卡住的点高度集中在三处第一是没看透题目的本质模型想不到该用什么数据结构去维护第二是想到了正确的数据结构但在实现细节上写出超时版本第三是没想到离散化或者数据范围压缩这一步导致内存或者复杂度直接爆炸。这三类问题其实反映了同一个本质T3考的不是“你会不会某个算法”而是“你在有限时间内能不能把一道陌生题转化成熟知模型并且写出能过的代码”。这恰恰是很多平时刷题依赖题解、缺少独立思考的人最薄弱的地方。所以被T3卡住并不丢人关键是要赛后把这道题彻底吃透下次遇到同类题目能形成条件反射。2. 题意拆解与问题转化2.1 从题目描述中提取关键约束这类T3题目的描述往往绕了几个弯把核心问题藏在故事背景里。我当时在赛场上花了大概三到四分钟读题第一遍读完其实是有点懵的因为描述里的操作听起来挺复杂。但读第二遍的时候我会下意识地做一件事把题面里的名词翻译成数据结构和算法的术语。不管是哪一场双周赛T3读题时都建议遵循以下步骤。先把输入规模圈出来数据范围决定了你能用什么复杂度的算法——这是最重要的一条信息。如果数据范围在10的5次方量级基本就告别了O(n²)的暴力解法必须想O(n log n)的方案。再把操作类型分个类是单点修改、区间查询还是成对匹配、全局统计。最后问自己一个问题这个题如果没有任何特殊条件暴力解是什么暴力解的复杂度是多少超时的瓶颈出现在哪里2.2 识别题目背后的经典模型这一环节是整道题的题眼。大部分T3题目都可以归入某几个经典模型的变体区间问题会想到线段树、树状数组、差分配对问题会想到排序加双指针、优先队列子数组或子序列问题会想到动态规划前缀和统计类问题会想到哈希表加排序。174场双周赛的T3就是典型的“配对加统计”模型它的核心操作本质上是在维护一个有序集合并且在满足特定条件时进行配对删除。这个模型你看着可能陌生但如果说“用平衡树维护有序集合配合前后驱查找”刷过题的朋友应该就能反应过来。赛后我和几个做了这道题的朋友聊发现最快的人一眼就识别出了这个模型直接把代码往里套而卡住的人大多是试图用模拟的思路硬解结果代码越写越复杂。所以我一直强调刷题刷的不是题量而是“模型库”的丰富度。你能在脑子里存储多少种模型以及它们的变体决定了你在赛场上识别题眼的速度。这道T3给我最大的警醒就是赛前多过几遍常见数据结构的经典套路比临时刷一堆难题管用得多。3. 算法选型与复杂度推演3.1 暴力解法的瓶颈分析我在赛场上拿到这道题后第一反应是尝试建立一个朴素的模拟方案用一个列表维护当前所有未匹配的项每次来一个新项就遍历整个列表去寻找可以匹配的项。如果找到了把它从列表里移除如果没找到就把新项加入列表。这个方法正确性没问题但复杂度是O(n²)。我快速估算了一下如果数据量上到了10的5次方最坏情况下需要执行10的10次方次操作这在LeetCode的评测环境下是绝对不可能通过的。为什么这个暴力算法会这么慢因为每次匹配尝试都需要扫描整个列表大量时间浪费在“查找”这个过程上。列表越大单次查找越慢而随着操作的持续列表的长度基本维持在一个较高的水平上。从这件事能看出来一个重要的思维习惯拿到题目先写暴力解的好处是帮你验证对题意的理解是否正确但它的意义也只到此为止。关键在于你要能从暴力解的弱点出发反推出优化方向。暴力解慢在“查找”那优化的核心自然就是“如何让查找变快”。3.2 从O(n²)到O(n log n)的优化路径当我把优化目标锁定在“快速查找可匹配项”之后脑子里立刻浮现出几个候选数据结构哈希表、树状数组、有序集合。哈希表的优势是O(1)时间内的精确查找但如果需要查找的是一个范围内的项哈希表就无能为力了。树状数组适合处理前缀和与区间频率统计但它的维护逻辑在配合删除操作时会相对琐碎。最终我把目光落在有序集合上。有序集合本身就是平衡树的一种包装支持O(log n)的插入、删除、查找最关键的是支持在一个值附近快速找到前驱和后继。对这道题而言每次来一个新项我只需要在集合里查找它最接近的匹配项检查是否满足匹配条件如果满足就删除并计入答案如果不满足就插入集合。每一步操作从O(n)降到了O(log n)整体复杂度O(n log n)完全在安全范围内。这里我特别想强调一个决策原则复杂度选型的核心依据是数据范围不是个人偏好。10的5次方以下的数据量O(n log n)是稳妥的选择过了10的5次方就要考虑是否存在O(n)的哈希方案。我在赛场上选有序集合是因为它实现起来快捷代码量少不容易出边界问题。赛后的补题复盘里我也验证了另外一种基于双堆的方案逻辑上等价但实现上更繁琐最终并没有采用。4. 核心数据结构的选择与实现细节4.1 有序集合的选型理由现在很多编程语言的标准库都内置了有序集合但细节差异很大选错了实现方式就可能翻车。就拿最常见的两种语言来说C的集合是基于红黑树的提供稳定的对数复杂度操作Python虽然没有内建的有序集合但我们可以求助于第三方的有序容器库。对于其他语言情况也是形形色色——有些有内置的有序集合有些只有排序数组都需要灵活变通。为什么这道题非要有序集合不可因为题目要求的匹配操作本质上是在集合中寻找“最合适”的项而“最合适”的定义往往落在某个值区间内。有序集合可以在O(log n)时间内完成两件关键操作第一是快速定位某个值的插入位置第二是找到某个值附近的前驱或后继。这两个操作是平衡树天然支持的而在普通的哈希表上实现起来非常别扭。4.2 实现中的几个关键细节有了数据结构只是第一步真正让代码在时限内跑过的是那些藏在角落里的细节。第一个细节是处理重复项时要注意集合里存的到底是一个唯一的标识符还是一个值当存在多个相同值时你是否需要额外维护某种计数关系。这个问题一不小心就会导致匹配错误我在补题时就亲眼见过有人因为重复项的计数搞混答案差了好几个。第二个细节是匹配的优先级问题。当集合中有多个可以匹配的候选项时选择哪一个会直接影响后续操作的正确性。这里有两种策略一种是最小差值优先也就是贪心地选择差值最小的项另一种是任意可匹配即可。如果你为了省事选了任意匹配那必须严格验证这是否会破坏题目要求的全局最优性。赛时我最初按任意匹配写的几行代码在构造测试用例面前直接暴露出反例被迫改成维护有序的候选集合。第三个细节是最容易被忽略的边界条件的控制。当集合为空时、当前项没有任何可匹配项时、匹配后集合只剩下一个元素时这些场景必须在代码里被清晰地覆盖。随手翻了翻我的提交记录第一次超时的版本就死在了一个边界条件上某次插入操作在寻找匹配项时越过了集合的末尾直接访问到空引用导致空指针异常。5. 代码实现与逐段解读5.1 核心逻辑的实现方案我在这里给出一个核心逻辑的伪代码框架它不绑定具体语言方便大家迁移到自己的主语言里。维护一个有序集合 s 答案计数 ans 0 对于输入序列中的每一个元素 x 在 s 中查找 x 的前驱 pred 和后继 succ 如果 pred 与 x 满足匹配条件从 s 中删除 pred ans 1 否则如果 succ 与 x 满足匹配条件从 s 中删除 succ ans 1 否则将 x 插入 s 返回 ans这个框架的精髓在于“先查前驱再查后继”的顺序。为什么不是随便查一个因为在某些匹配规则下前驱和后继都可能是合法匹配项但选择不同会带来完全不同的后续结果。固定一个明确的优先级顺序可以保证代码行为是可预测的。我在赛场上用前驱优先的策略跑通了所有样例但我也知道在某些规则下后继优先才是正确的。这个没有定律可背完全取决于题目的具体约束。5.2 各语言实现的注意点如果你用的是C有序集合可以直接用标准库的集合容器。它的查找、插入、删除都是O(log n)。在使用它的时候注意一下查找前驱后继的方法标准库里有专门的下界和上界查找函数搭配使用就能拿到插入位置左右两边的元素。如果你用的是Python内建的数据结构里没有直接可用的有序集合。我见过有人用堆来做同时维护一个最大堆和最小堆再配合延迟删除来模拟有序集合。这个方案的思路是巧妙的但实现复杂度会显著上升调试起来也更痛苦。如果你在比赛环境下可以引入第三方库那直接用现成的有序数据结构就省心很多。我个人不推荐在赛场上手写一个平衡树除非你平时就有用纯Python手写红黑树的习惯否则大概率会写出比标准库慢得多的版本。5.3 复杂度与正确性的最终确认按照上面的框架实现整个算法的复杂度是三部分的总和遍历输入序列是O(n)每次插入和删除是O(log n)整体最坏情况也就是O(n log n)。对于这道题的数据范围来说这个复杂度是绝对安全的。正确性方面我在补题时专门写了一个小型的暴力验证脚本用随机生成的小规模数据跑了几百组对比一边跑朴素模拟一边跑优化后的版本逐一比对接下来的操作结果。这个方法几乎是我每一次做T3题目之后的固定动作。它能快速揪出那些“只在极端数据下才出现”的逻辑漏洞而手工构造的测试用例往往覆盖不到这些情况。我强烈建议每一个刷题的人养成这个习惯写完高效版本之后不要急着收工花几分钟暴力对拍一下能省下赛后排名出来之后的后悔。6. 赛时复盘几个关键决策点的回顾6.1 读题阶段的决策我在174场双周赛上实际的时间线是这样的开场先粗略浏览四道题的全貌T1和T2一眼看到底确定是简单题先放一放重点看了T3和T4的描述。T4的题干明显更长限制条件更复杂我判断这题的思考成本太高决定先攻T3。这个决策事后看是正确的T4我在赛后看了别人讨论确实需要相当深的算法功底就算我在赛场上多花二十分钟也未必能做出来。读T3题目时我花了大约两分钟把题面里的“故事”剥离掉还原出核心的数据操作。这里有一个小技巧可以分享读题时拿一支笔把题面里所有的名词圈出来然后翻译成数据结构术语。比如把“仓库里的箱子”翻译成“集合中的元素”把“往仓库里放箱子”翻译成“插入操作”把“找出最合适的箱子配对”翻译成“查找并删除”。这套翻译动作做完题目的骨架就出来了。6.2 编码阶段的决策代码层面第一个决策是语言选择。我当时直接选了C原因无他标准库自带有序集合容器写起来最顺手。在双周赛这种限时环境下选择自己最熟悉、标准库最完备的语言是一种合理的策略而不是去纠结“哪个语言的代码量更短”。第二个决策是接口设计。我没有把题目的全部逻辑写在一个大函数里而是把有序集合的维护逻辑独立封装成一个类。虽然这道题的体量并不需要多复杂的类设计但独立封装有一个好处调试时可以在类的方法里打印出集合内部状态清楚地看到每一步操作前后的变化。我在赛时调试过程中正是靠这种方式发现了一个删除逻辑中的反复问题。第三个决策是“宁可多写一两行不贪图简洁而牺牲清晰度”。我看到有些选手喜欢用非常紧凑的链式调用把代码堆成一行看起来虽然很酷但一旦出错定位问题的时间成本会直线上升。在关键逻辑处多写几个临时的中间变量能让你在代码出错时更快地发现问题所在。6.3 时间分配与心态管理说实话我在T3上并不算特别顺利。第一次提交因为边界条件问题答案错误返回的错误信息显示我匹配了不该匹配的项。这时候距离比赛结束还有约二十分钟。我给自己定了一个底线如果十分钟内定位不到问题就暂时跳去把T1和T2交了至少保住两题然后再回来继续磨T3。庆幸的是我在检查代码时发现问题出在判断匹配条件时漏掉了一个比较符号。修正之后再提交就直接通过了。整个T3从读题到通过大约花了二十三分钟。这里想给所有打比赛的朋友一个心态上的建议双周赛不是一锤子买卖不必因为一道题卡住就慌了神。合理分配预算、设置止损点比死磕一道题更有利于全局成绩。T3是重要但没有重要到值得你放弃T1和T2的稳妥分数去孤注一掷。7. 训练建议如何系统提升双周赛T3的通过率7.1 建立自己的模型库与套路总结如果你发现自己总是在T3上卡壳问题往往不在于“脑子转得慢”而在于“模型库容量不够”。什么意思呢就是当你看到一道题的时候脑子里调不出来与之匹配的已知解法库。刷题多的人并不是天赋有多高不过是见过的模型更多条件反射更快而已。我建议做一个自己的“模型笔记”每做完一题记下三个东西第一这道题属于什么模型区间、配对、最值、计数第二题目的包装是什么是数组、是字符串、是树第三这个模型对应哪些标准解法每个解法的适用数据和复杂度边界是什么。模型笔记积累到四五十条之后你会发现自己读题的速度和对题面的敏感度会有一个质的飞跃。针对双周赛T3的题目特征特别值得多总结的数据结构包括有序集合类问题、树状数组与离散化、双堆维护动态中位数、差分数组配合扫描线。这些都是T3的高频考点。7.2 模拟赛训练与时间压力适应平时刷题和比赛是完全不同的体验这一点必须正视。平时刷题时你没有时间压力可以慢慢想、反复调试甚至中途查阅资料比赛时会在时间压力和排名焦虑的双重挤压下暴露出各种问题。因此我特别推荐定期做整套的模拟赛训练。模拟赛的具体做法是找一套往期的双周赛题目定好一个倒计时然后按照正式比赛的规则去做。过程中不允许暂停不允许查资料只允许用本地编辑器和评测的在线判题。做完之后不管成绩如何都要记录一下自己每个题花费的时间然后对比目标时间进行分析。我在这个过程中发现了一个有意思的规律很多选手并不是不会做T3而是把太多时间耗在了T2的完美解法上。T2本身难度不算高但要写出一个完整无误的解法可能得多花十分钟而如果这十分钟用更简单的思路快速通过省下来的时间正好够T3的思考。所以模拟赛的一个重要训练点就是学会在简单题上主动放弃完美方案用“能过就行”的解法快速拿分。7.3 补题与复盘的具体方法赛后的两小时是黄金时间。不管比赛成绩如何我建议趁热打铁把没做出来的题目彻底搞懂并亲手实现一遍。补题不是“看一遍题解就算补完”那只是在自我安慰。真正的补题标准是关上题解和讨论区凭借自己对题意的理解和刚才看到的思路方向独立写出完整可运行的代码并通过全部测试用例。复盘时要特别关注那个“从卡住到想通”的转折点。回想一下到底是什么信息让自己豁然开朗是某个讨论里的一句话、题解里的某张示意图还是比赛结束后的灵光一闪把那个关键信息记录下来它就是你的下一次比赛时的“触发词”。我在T3的复盘笔记里就记着一句话“操作可以抽象成有序集合前后驱判断——看到匹配类操作优先想有序集合。”7.4 保持稳定的刷题节奏最后想说的其实是老生常谈但确实管用的一点保持稳定的刷题节奏远比偶尔刷一天高强度然后歇三天更有效。双周赛的通过率不会因为你连续刷了二十道难题就突飞猛进但如果你能坚持每周做两到三道中等偏上的题目并且认真走完“做题、卡住、看懂、复盘、记录”的完整闭环一个月之后回头对比进步会是肉眼可见的。说一下我个人对T3这类题目的真实态度它确实让人焦虑因为你永远不知道自己是否能在比赛时间内把思路理清。但换个角度来看正是这种不舒适区的存在才让双周赛有了训练价值。如果把把比赛都是已经会的套路那比赛就只是纯粹的码字速度测试那样的刷题还有什么乐趣可言呢。我自己的补题库里至今躺着好几道T3是我第一次没做出来的。每隔一段时间翻出来重做一遍对比一下现在的做题速度和思维清晰度那种“我自己能感觉到我在变强”的时刻可能才是坚持刷题这件事最上头的部分。希望这篇文章里的拆解思路和复盘方法能帮你下次在双周赛T3上少卡一会儿。

LeetCode双周赛T3分水岭：有序集合模型识别与O(n log n)优化

相关推荐

STM32L4S5ZI+PCA9422：低功耗电源管理方案全解析

可儿瑞慈童装加盟曲靖市门店童装品牌代理提供整店输出与运营培训支持

口碑好的真皮沙发换皮翻新服务商筛选名录

更多资讯

2026年降AI率工具真实测评：10款改写工具的优劣与使用边界

BigBanana AI Director：一站式AI短剧与漫剧导演平台工程实践

BigBanana AI Director：工业级AI短剧与漫剧全流程制作实战指南

深入理解Spring三级缓存：循环依赖的机制、局限与排查实践

用编程思维打造个人知识体系：IoC、依赖注入与响应式学习实操指南

联邦学习赋能大模型WAF：破解数据孤岛与攻击变异难题

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？