最近被好几个同学问同一个问题数据结构课到底怎么学才能不算白学我的回答一直很固定——去OJ刷题。注意不是让你像个无头苍蝇一样乱刷量而是把“数据结构OJ习题”当作检验自己是否真正理解某个结构的试金石。上课听懂顺序表和链表和你能在五分钟内用代码把链表反转干净利落写出来是两码事。OJ的价值在于它不会陪你演戏代码跑不过就是跑不过超时就是超时答案错就是错机器比人诚实得多。这篇内容不是教程汇总是我自己刷题、也带过别人刷题之后沉淀下来的实操经验。适合三种人看第一种刚学完数据结构、想做OJ却不知道怎么下手的初学者第二种刷了几十道题但老是卡在WA和TLE上、找不到突破口的进阶选手第三种准备考研机试、实习笔试需要短期高效复习数据结构的人。本文会从出题套路、选题策略、AC模板、判题结果排查这几个角度把“刷OJ”这件事拆开揉碎讲清楚。1. 数据结构OJ到底在练什么先看懂出题人的套路很多人以为OJ习题是“数据结构教材课后题的电子版”这个认知害了不少人。教材课后题练的是“你会不会背这个结构”而OJ题练的是“你会不会在合适的场景里用这个结构”。这两者差距非常大。出题人不会在题目里告诉你“这题请用栈”他只会给你一个场景让你自己判断该用什么结构。所以刷OJ的第一步不是急着写代码而是先学会识别题型套路。1.1 五大高频结构每一章都在考哪些题型数据结构课程的主线章节基本就围绕线性表、栈队列、树、图和查找排序这几块。对应的OJ题型也高度集中摸清以后你看到题目能迅速定位考点数组与链表双指针、快慢指针找环、链表反转、合并有序链表、数组的区间操作、二维矩阵模拟。这类题目看起来是在考“你会不会遍历”实际上是在考指针操作的边界意识。栈与队列括号匹配、表达式求值、单调栈求下一个更大元素、单调队列求滑动窗口最值、用栈模拟队列、用队列实现栈。这部分的套路非常固定一旦掌握了模板性价比极高。二叉树三种遍历的递归与迭代、层序遍历、二叉树最大深度、最近公共祖先、判断二叉搜索树、路径总和。二叉树的题型是递归思维最好的训练场。图邻接表的存储、无权图的最短路BFS、连通分量计数、拓扑排序、判断是否有环。图的题一看数据规模二看是不是稀疏图这决定了你该用邻接矩阵还是邻接表。查找与排序二分查找的边界处理、快排的partition思想、堆排序、Top-K问题、哈希表的应用。这类题目经常和数据结构的其他章节结合起来考。为什么强调“识别套路”因为我在辅导A同学刷题时发现他最大的问题不是不会写代码而是拿到一道题完全不知道往哪个方向想。后来我让他每做一道题先写在题目旁边标注“这题考的是XX结构、XX思路”坚持两周以后他自己看到“求滑动窗口最大值”就能条件反射地想到单调队列。这就是套路识别的效果——把无规律的题目归纳成有限的模板做题速度会快非常多。1.2 复杂度意识OJ的时限究竟在逼你做什么OJ和本地IDE最大的区别就是它有限定的时间限制通常1到2秒和内存限制通常64MB到256MB。这意味着你不仅要写出“对”的代码还要写出“够快”的代码。很多同学本地跑通样例就提交结果一看TLE超时还一脸懵明明结果对啊。这里有一个简单粗暴的经验法则假设评测机一秒能执行大约10的8次方次简单运算那么数据规模n10万的时候O(n²)的算法约要执行100亿次运算必然超时O(n log n)的算法只要大约170万次轻松通过。所以拿到题目先看数据范围这一步比写代码更早n≤10³O(n²)甚至O(n³)都可以接受。n≤10⁵必须O(n)或O(n log n)。n≤10⁷基本只接受O(n)。n≤10⁹一般是在考数学公式或者二分、快速幂这类对数级算法。我在实际中见过最典型的例子是一道“统计数组中每个元素右边第一个比它大的元素位置”的题n10万。某人一开始用两重循环暴力做本地测小数据全对一提交就超时。后来换成单调栈从O(n²)降到O(n)瞬间AC。那道题给我们的教训是OJ不关心你思路多辛苦它只关心你的算法在极限数据下能不能跑完。养成看数据规模再定算法的习惯能帮你规避掉百分之六十以上的超时问题。2. 选题与节奏刷OJ最该避开的三个误区刷OJ这件事方向比努力重要。很多人坚持了两个月刷了两百道题效果却不如别人认真刷五十道差别就在选题策略和复盘方式上。下面这三个误区是我自己踩过、也看别人反复踩的先帮你排掉这些坑。2.1 按知识点横向推进而不是按题目序号硬刷新手最常见的做法是打开题库从第1题开始按顺序往下做。这看起来很努力实际上效果很差。因为OJ的题序是按难度或者入库时间排的知识点跳跃极大。今天做一道链表题明天做一道数学题后天又来一道字符串知识点之间没有连续强化等你刷完十道题链表早忘干净了。我的建议是“纵向攻克、横向推进”按数据结构的知识点分组每个组两周之内集中刷10到15道题从简单题开始逐步过度到中等难度暂时跳过难题形成知识模块的“手感”以后再进入下一个模块。比如第一组刷线性表顺序表、链表第二组刷栈和队列第三组刷二叉树如此类推。这样做的好处是把 “短期记忆转长期记忆”所需要的重复次数集中起来而不是分散在几个月里每次刚有点感觉就切换到新知识点。具体到每组内的顺序也有讲究。我一般建议每组先做两三道最直白的“模板题”比如链表组先做“反转链表”和“合并两个有序链表”这些题就是单纯考操作不给场景包装。等模板题能默写了再去做“判断链表是否有环”“两两交换链表中的节点”这类需要一点理解的应用题。这样由易到难组内梯度合理不容易劝退又能保证每个知识点练透了。2.2 以8周为周期的专题推进计划如果你不确定整体节奏怎么安排可以直接参考下面这个8周计划。这是我给几个学弟学妹用过的方案适用于非竞赛向、以掌握数据结构为核心目标的学习者每周投入大约8到10小时周次主题建议完成量核心练习点第1周数组与链表10~12题双指针、链表反转、快慢指针、删除重复元素第2周栈与队列8~10题括号匹配、单调栈入门、用栈实现队列第3周二叉树入门8~10题递归三种遍历、层序遍历、最大深度第4周二叉搜索树与堆6~8题验证BST、中序遍历、优先队列Top-K、堆排序第5周图论基础8~10题邻接表建图、BFS最短路、DFS连通分量第6周图论进阶6~8题拓扑排序、判断环、二分图染色第7周二分与排序6~8题二分边界、快排思想、归并排序统计逆序对第8周综合模拟5~8题混合考点题、往年真题、限时自测这个计划的核心逻辑是“先结构后算法”。前六周围绕数据结构本身第七周加入二分和排序是因为这两个主题是数据结构应用的延伸放在后半段能帮你建立“结构算法”的综合视角。第8周的限时自测特别重要建议每道题控制在30到40分钟不会做就标记不要死磕到底——限时才能模拟真实考场和笔试环境。我特别要强调一点计划里的完成量是“下限”不是“上限”。如果你某周发现做得很顺手可以多做一些如果卡得很厉害宁可少做几道把每道题都搞透也不要为了数量赶进度。刷OJ的质量远比数量重要这个观念越早建立越好。3. 五类高频题型的AC模板与易错点可直接复用刷数据结构OJ其实有不少“公式化”的写法。这些模板不是我发明的是无数人踩坑之后沉淀下来的通用写法。掌握模板最大的价值不是让你背代码而是让你把大脑从“怎么实现基础操作”中解放出来把注意力集中在“这题要怎么变形”上。下面五个方向是我觉得性价比最高的背熟它们能覆盖OJ里相当比例的题目。3.1 链表操作虚头结点、反转与快慢指针链表题是国内数据结构OJ的重灾区不是因为它难而是因为指针操作太容易出错。我最推荐的第一个技巧是“虚头结点dummy node”。凡是涉及头结点可能被修改的操作比如删除头结点、在头部插入都先创建一个虚拟头结点指向真正的头结点最终返回dummy-next。这能省掉大量的if判断边界情况。链表反转是另一道必背模板。正确写法是迭代中始终保持“先保存下一个节点再改当前节点的next”很多新手错在先把cur-next改了结果下一个节点的地址丢了链表直接断掉ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 关键先保存后继 cur-next prev; prev cur; cur nxt; } return prev; }快慢指针解决“判断链表是否有环”“寻找链表的中点”这类问题也极好用。判断环的思路是快指针每次走两步慢指针每次走一步如果快指针最终追上了慢指针说明有环如果快指针先走到空说明无环。这里有个容易犯的错while循环条件要同时判断fast和fast-next是否为空因为快指针一次走两步如果fast指向空再访问fast-next会直接RE。写的时候一定要先判断fast是否为nullptr再判断fast-next。3.2 单调栈与单调队列经典滑动窗口模板单调栈是栈这块最值钱的考点没有之一。它的经典场景是“求数组中每个元素右边第一个比它大的元素位置”。朴素做法是两重循环O(n²)用单调栈可以降到O(n)。核心思想是维护一个栈底到栈顶递减或递增的栈遍历数组时当前元素不断与栈顶比较只要栈顶元素小于当前元素说明栈顶的“右边第一个更大元素”就是当前元素于是弹出栈顶并记录答案。单调栈的代码模板非常短难的是理解它为什么能做对。可以这样想栈里存的是“还没找到答案的元素下标”。当新元素比栈顶大时它就成了栈顶的答案若比栈顶小就继续压栈等待。每个元素入栈一次、出栈至多一次所以总复杂度O(n)。单调队列的经典应用题是“滑动窗口最大值”。做法是用双端队列维护窗口内元素的下标保持队头元素始终是最大值并且窗口滑出时及时弹出过期下标。这里有个特别容易搞混的点队列里存的不是值是下标比较大小要拿值来比判过期要用下标算。每次窗口右移先把队尾所有比新元素小的值弹出因为它们“又小又老”以后用不上再压入新下标最后把队头已经滑出窗口的下标弹出那么当前队头就是窗口最大值。我在给A同学讲这块时用了排队买奶茶的类比新来的顾客如果又高又年轻更大且更新那前面矮的顾客在“窗口期”内永远轮不上直接淘汰而队头那位如果排队时间太久已经出了窗口也直接走人。这样一来队头永远是当前窗口里“最有资格”的顾客。类比一到位代码就再也不容易猜了。3.3 二叉树遍历递归转迭代的写法与思路二叉树的三种遍历递归版本写起来都很短但OJ经常卡递归的栈空间或者考察你能否手动模拟栈。所以迭代写法必须会。以中序遍历为例思路是“一路向左入栈走到最左边后弹出并访问再转向右子树”——这就模拟了递归调用栈的行为vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }前序遍历的迭代稍微简单一些可以用“先压右子树再压左子树”的方式因为栈是LIFO后压的左子树会先出栈后序遍历更麻烦一点常见做法是用两个栈或者用一个反转思路先做“根-右-左”再反转为“左-右-根”。如果时间紧记住中序和前序的迭代写法已经能覆盖绝大多数考到“手动栈遍历”的题目。做二叉树题还有一个不可忽略的入门常识递归写法虽然可能爆栈但在OJ数据规模较小时依然是首选因为它不容易写错。我一般建议数据规模n在几千以内用递归没问题超过一万并且树退化成链比如斜树就要当心递归深度过大导致栈溢出这时要改成迭代。3.4 图论基础邻接表BFS最短路模板图论题在数据结构课程里一般不会考太难最常出现的是无权图的最短路即BFS和连通分量计数。建图方式选邻接表还是邻接矩阵直接决定了内存够不够。n1万条边以内的小图可以用邻接矩阵n10万级别的稀疏图再用int数组开n×n的矩阵必挂MLE必须用vector 邻接表。BFS求无权图最短路模板如下核心是用dist数组记录起点到每个点的最短距离同时用vis标记防止重复入队void bfs(int start, vectorvectorint graph, vectorint dist) { queueint q; dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : graph[u]) { if (dist[v] -1) { // 没访问过 dist[v] dist[u] 1; q.push(v); } } } }这里的dist初始化成-1既当“是否访问过”的标记又当最短距离存储一份数组两种用途很省事。注意BFS是按层扩张的所以第一次访问到某个节点时记录的dist一定是最短的——这是BFS的性质保证的不需要额外的比较更新。看到“最短”“最少步数”这类词优先考虑BFS看到“是否存在”“有多少个连通块”优先考虑DFS或并查集。3.5 并查集与堆两个高频“工具型结构”并查集是一个非常精巧的结构在OJ中经常以“判断两个节点是否连通”“统计连通分量数量”的形式出现。完整模板包含两个优化路径压缩和按秩合并。路径压缩是核心它让每个节点在find时直接指向根节点使得后续查找接近O(1)按秩合并则是把矮树接在高树下面防止树退化成链。int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路径压缩 return parent[x]; } void unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return; if (rank[ra] rank[rb]) parent[ra] rb; else if (rank[ra] rank[rb]) parent[rb] ra; else { parent[rb] ra; rank[ra]; } }用并查集容易踩的坑有两个一是忘记初始化parent[i] i二是unite时直接改parent[a] b而不是让两个根节点去合并导致路径压缩失效。每次写并查集前先做初始化循环这是肌肉记忆。堆在OJ里最常通过优先队列priority_queue来使用。默认是大顶堆需要小顶堆时要自定义比较器。做“求第K大的元素”“合并K个有序链表”这类Top-K问题优先队列是标配。这里要记住一个原则Top-K问题中K远小于n时与其全部排序O(n log n)不如维护大小为K的小顶堆O(n log K)内存和速度都更优秀。4. 被OJ判题结果支配的恐惧WA与TLE排查实录刷OJ的人没有没被判题结果伤害过的。WA、TLE、RE、MLE每种结果都对应不同的代码问题。这一节我把自己实际遇到的、以及辅导别人时反复见到的典型问题整理成速查表再展开讲几个真实案例。4.1 WA、RE、MLE分别暴露了哪些代码问题先上速查表方便你直接对照排查判题结果常见原因排查思路WA答案错误初始化遗漏、边界条件判断错、多组输入没清空容器、数据溢出检查全局变量和循环内变量是否复位构造最小边界测试把int换成long long看是否通过TLE超时算法复杂度过高、死循环、输入输出方式太慢先看数据范围评估当前复杂度检查循环终止条件改用scanf/关闭流同步RE运行错误数组越界、空指针解引用、递归栈溢出、非法内存访问检查索引是否超过容器大小确认访问节点前做了空判断递归改迭代MLE内存超限开了一个过大的数组、二维矩阵浪费空间把全局大数组改为动态容器邻接矩阵换成邻接表用滚动数组压缩WA是最让人头疼的因为样例能过但结果就是不对说明你漏了某些特殊情况或者边界。我印象很深的一道题统计一段字符串里不重复字符的最长子串A同学写的代码在样例和小数据上全对但一提交WA。我们花了半小时排查最后发现是他的哈希表更新逻辑没有处理“上一次出现的字符已经在当前窗口之外”的情况导致窗口起点判断错误。这种错误在本地随便造几个小数据根本试不出来得专门构造那种“字符跨越多个窗口”的用例才能暴露。从那以后我养成了一个习惯WA之后先不急着看代码而是构造边界数据——空输入、只有一个元素、两个相同元素、数据全是最大值、n取上限——这些用例往往一击致命。RE里面最坑的是递归爆栈。C默认递归栈大约1MB不同评测环境可能不同但量级差不多深度几十万到百万就会溢出。二叉树退化成链时深度等于节点数10万个节点就能让递归崩溃。碰到这类题要么显式提高栈空间有些OJ支持编译选项要么改成迭代写法后者更稳妥。MLE则是空间意识的问题。我见到最典型的一个错误是在n10万的问题里开了int dist[100005][100005]结果当然是内存爆到妈都不认。正确的思路是凡是能用一维数组解决的问题不用二维能用邻接表不用邻接矩阵能用动态数组不用定长二维数组。数据结构课程里图论题的那个“邻接矩阵脑”在OJ真实环境里必须改掉。4.2 一个TLE转AC的优化实战记录有一次我带A同学做了一道看似不难的题给定一个长度为n的数组求每个位置左边第一个比它小的元素位置。他的第一版实现是两重循环n10万时果然TLE。我们做的优化思路如下。第一轮先分析这道题和“右边第一个更大元素”是镜像对称的都能用单调栈解决。它的核心是维护一个栈底到栈顶递增的栈遍历数组时栈顶就是当前元素左边第一个比它小的候选值。如果栈不空且栈顶值大于等于当前元素就持续弹出直到栈空或栈顶小于当前元素此时栈顶即为答案随后把当前元素下标压栈。这个替换看起来只是把内层循环去掉了但本质上复杂度从O(n²)降到了O(n)。为什么能保证正确因为每个元素入栈出栈恰好一次当我们要找左边第一个更小元素时栈内维护的是“尚未被更大/相等元素淘汰的、递增的候选序列”栈顶必然是最接近当前元素的符合条件的值。改写完成后同样的数据瞬间通过。这道题的复盘价值在于很多时候TLE并不意味着代码逻辑错误而是“你选择了错误的工具”。两重循环的写法在思路上没错暴力也算一种答案但比赛和OJ永远只认更优的解法。所以遇到TLE先别忙着优化常数、微调循环先想想算法整体能不能换一种结构——这就是数据结构习题存在的意义逼着你在“会做”和“做得快”之间建立连接。4.3 数据对拍没有比赛环境也能自测的正确姿势在本地手测几组小数据就提交命中率低是正常的。真正专业的做法是“数据对拍”写一个肯定正确的暴力程序、一个你要测试的优化程序再加一个随机小数据生成器不断生成数据喂给两个程序比对结果。有一点不同就说明优化程序有问题再调试定位。具体的做法大概是用Python写个脚本生成n在1到20之间的随机数组数据小时暴力程序跑得动又足以暴露边界问题同时跑优化程序和暴力程序比较输出是否一致。循环几百次能发现绝大多数手写测试发现不了的隐蔽错误。这个方法不需要多高深的技术但对提升AC率极有帮助。对拍的核心价值在于“用机器的随机覆盖代替人的有限想象”。人构造用例时总是不自觉地偏袒自己代码的思维路径随机数据则完全不受这些约束越是从没想过的输入越容易暴露出代码里潜藏的错误。我自己的习惯是一道题卡了超过二十分钟还找不到WA原因就写对拍往往十分钟内就能锁定问题行。5. 比AC更重要的事输出题解与代码习惯养成刷OJ这件事刷到后期你会发现真正拉开差距的不是AC数量而是你怎么对待已经做过的题。我见过太多人一道题AC了就不再回头看一眼刷了上百道过两个月全忘了跟没刷一样。这就引出了刷OJ最容易被忽视的三件事写题解、复盘错题、规范代码习惯。5.1 为什么写题解比继续刷下一道更重要把一道题AC以后花十五分钟写一篇简短的题解价值可能比你继续刷三道新题还高。题解不需要写得多华丽只需要回答三个问题这道题考了什么知识点我最初为什么没做出来或者卡在哪一步如果让我重新做我会用什么思路。写的过程逼着你把零散的“运气AC”变成有意识的“方法论总结”。我辅导A同学时给他立了一个规矩每天最多做三道新题但每道题必须写五到十行题解写在文档里。坚持一个月后他发现自己的进步速度反而比之前“一天刷十道”更快。原因很简单写题解就是一次自我复盘把大脑隐性的思考过程显性化。下次遇到类似题目他不再需要从头想而是直接调用之前总结过的模板和套路这就是“熟能生巧”的真正原理。5.2 代码风格变量命名和边界处理习惯直接影响调试效率代码风格在OJ里似乎不影响AC但它直接影响你排查问题的速度。命名规范的代码比如用left/right而不是l/r用isValid而不是flag调试时你一眼就能看出变量含义命名混乱的代码出错了连自己都得读半天。我见过有人把整道题的状态都压缩成一个int变量来存结果WA了以后完全无法定位最后只好重写。另外建议养成两个固定习惯所有涉及边界比较的地方统一的写法要么是“小于”要么是“小于等于”别混着用所有循环不变的量提前用变量保存比如容器大小size()避免每次循环重复调用耗费时间。这两个习惯看似微小但能显著降低出错概率。尤其二分查找的边界问题很多WA都出在then/else判断条件不一致上。5.3 建立自己的错题本两周后重做一遍刷题最忌讳的是“一锤子买卖”做对了就扔做错了改完就扔。更好的做法是维护一个错题文档记录每道错题的错误类型、原因、解决思路。然后隔一到两周把这些错题重新做一遍。重做时你会发现有些题你依然会卡在同一个地方这就是你的思维盲区能顺利AC的说明这个知识点已经真正变成你自己的了。这个习惯的执行成本很低但效果非常显著。因为大多数人在OJ上犯的错误都集中在特定几类——边界处理、初始化遗漏、复杂度过高——通过错题重练你能把自己的“易错类型”精准识别出来然后有针对性地克服。这比漫无目的地刷一百道新题高效得多。我自己的体会是数据结构OJ刷到最后你收获的其实不只是“会做题”这个技能还有一层更重要的东西面对一个复杂问题时知道该从哪里下手、用什么工具去拆解。这种能力在以后写工程项目、设计系统、甚至是排一个复杂的bug时都极其受用。最后分享一个小技巧如果你今天遇到一道题卡了很久别急着翻题解把题目放下去外面走十分钟回来重新读一遍题——百分之八十的情况下你会在重新理解题意的那一刻突然找到突破口。卡住往往不是因为不会而是因为一开始就把题意理解偏了。