大家刷题的时候可能都遇到过这种“三连题”——前后几道题单独看似乎没什么关联但放在同一天练习里背后往往藏着一个清晰的编排意图。我拿到的这份2月1日练习计划第40到42题就是一组非常典型的三连一道哈希/投票题、一道滑动窗口题、一道数组翻转题。如果你正准备按顺序刷这三道题建议先别急着逐题做。先把三道题的定位搞清楚再动手效率会高很多。本文我会把这组题的核心解题思路、代码实现、边界情况和实测中容易掉的坑一次讲透适合刚刷完基础数据结构、想在数组和队列方向加深理解的人。无论你用的是JavaScript、Python还是Java核心思路都通用我会以JavaScript代码为主做演示。1. 40-42题放在一起刷才看出编排逻辑刚开始我也有点不理解这三道题的难度曲线看起来是波动的为什么非要排在一起等我真正把它们逐个过完才发现这套组合拳并不是随便排的。1.1 三道题各自是什么快速定档先把三题的基本信息列一下。题号题目核心内容主要考点推荐时间上限新手推荐时间上限熟手第40题给定一个整数数组找出其中出现次数超过数组长度一半的元素多数元素哈希表、摩尔投票15分钟5分钟第41题给定一个数组和一个滑动窗口大小求每个窗口内的最大值双向队列、单调队列、滑动窗口25分钟8分钟第42题给定一个数组和一个k值将数组循环右移k位取模运算、三次翻转、原地操作15分钟5分钟三道题里40题和42题都不难上手41题才是真正的分水岭。如果你三道题能在一个小时内全部写完并跑通那数组这类题的基本功算是过关了如果卡在41题超过半小时也很正常后面我会详细讲这个题的思路。1.2 从哈希到滑窗到翻转一整套算法思维训练按我个人的理解这三道题可以看作一条能力递进的链路第40题要求你先学会“用空间换时间”——哈希表把O(n²)的暴力统计降到O(n)。第41题要求你更进一步把空间压缩到O(k)并且用单调性优化入队/出队逻辑。第42题则要求你“摆脱额外空间”的思维惯性用数学规律原地修改数组。换句话说40题教会你“可以开额外空间”41题教会你“如何用更小的额外空间”42题则挑战你“尽量别开额外空间”。这样一串下来对数组类操作的掌控感会明显提升。这也是为什么我不建议跳着刷直接跳到自己会的题等于放弃了这套递进设计。2. 第40题多数元素核心是“占多数”这个约束怎么用题目本身很简洁给定一个长度为n的数组存在一个元素出现次数大于n/2找出这个元素。这个“大于n/2”的条件是全部题目的灵魂。很多人忽略它直接写哈希表统计虽然能过但不是这道题想让你练的东西。2.1 审题要点“过半”到底意味着什么我们先想一个极端情况如果数组中每个元素都不一样那么根本不存在多数元素但题目保证一定存在这就给了我们可以利用的强约束。多数元素有一个特别的性质把数组中任意两个不同的元素抵消掉剩下的元素中多数元素依然占多数。假设多数元素出现m次m n/2任意抵消一对不同元素后总数变成n-2多数元素剩余次数至少是m-1。由于m - 1 (n - 2) / 2依然成立所以它仍然是新数组里的多数元素。这个规律看着简单却是第40题最优雅解法——摩尔投票法——的理论根基。很多资料直接把代码甩出来却没有解释这一步导致大家看完稀里糊涂。2.2 哈希表解法直接但不一定最优哈希表解法很直观遍历一次数组用Map记录每个数字出现的次数遇到某个数字次数超过n/2就返回。function majorityElement(nums) { const countMap new Map(); const half Math.floor(nums.length / 2); for (const num of nums) { countMap.set(num, (countMap.get(num) || 0) 1); if (countMap.get(num) half) { return num; } } }这个写法的时间复杂度是O(n)空间复杂度也是O(n)。在绝大多数面试场景下这个答案是可以过关的但如果你是去参加侧重算法优化的大厂面试面试官大概率会追问一句“能不能用O(1)空间”这时候就该摩尔投票上场了。2.3 Boyer-Moore投票法现场推演一遍摩尔投票法的核心思想是维护一个候选元素和一个计数器。遍历数组时如果计数器为0就把当前数字设为候选元素计数器变为1如果当前数字等于候选元素计数器加1否则计数器减1。最后候选元素就是多数元素。function majorityElement(nums) { let candidate null; let count 0; for (const num of nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { count--; } } return candidate; }我建议你自己拿[2, 2, 1, 1, 1, 2, 2]手推一遍。推到中间的时候counter会变成0但没关系继续往下推最后一轮留下来的candidate一定是2。这个算法最反直觉的地方在于为什么最后留下的候选元素一定能保证是多数元素而不是某个恰好存活到最后的普通元素因为每次count减1都代表有一对“不同元素”被抵消了。多数元素的出现次数多于其他所有元素的总和所以它永远不可能是被完全抵消掉的那一方。2.4 极易混淆的变形如果没有“过半”约束很多刷题的人把摩尔投票法背下来之后遇到一道变体题就翻车“找出数组中出现次数最多的元素没有过半约束。”这种场景下摩尔投票法完全失效因为缺少“ n/2”这个保证时counter归零后留下的候选元素不一定正确。所以用摩尔投票法之前务必先确认题意中有“超过一半”的保证。如果没有那就老老实实回到哈希表或者用分割统计的思路。这一步审题失误比代码写错更可惜在笔试里往往要白丢不少分。3. 第41题滑动窗口最大值单调队列的“淘汰制”最见功力第41题是这三道题里最有分量的一道给定数组nums和滑动窗口大小k窗口每次向右移动一位要求输出每个窗口内的最大值。很多人第一反应是“每次窗口里跑一遍max”但这样写面试官脸上的表情往往耐人寻味。3.1 暴力解法为什么慢从O(n*k)说起最直白的写法是枚举所有窗口在每个窗口内用Math.max找最大值。function maxSlidingWindow(nums, k) { const result []; for (let i 0; i nums.length - k; i) { result.push(Math.max(...nums.slice(i, i k))); } return result; }代码看起来非常简洁。但问题在于如果数组长度n是10万窗口k是1万暴力解法的执行规模大约是10万×1万10的9次方次操作这还是在Math.max内部实现足够高效的前提下。现实中的线上场景比如一个数据流监控面板需要实时展示最近一分钟的峰值这种性能是完全不能接受的。暴力的慢不是因为Math.max本身慢而是它“忘记”了前一个窗口已经算出来的信息。前一个窗口的最大值和后一个窗口的最大值之间其实重复用到了k-1个元素暴力法把这些重复元素全部重算了一遍信息被白白丢掉了。3.2 单调双向队列的本质窗口里的“淘汰机制”想要避免重复计算核心思路是维护一个有序结构让每次窗口滑动时只需要处理“新进来的元素”和“被挤出去的元素”即可。这个时候就要引入双向队列。单调队列的规则总结起来就一句话队列里的元素按值从大到小排列队首永远是当前窗口的最大值。具体执行分三步新元素入队之前先把队尾所有小于等于它的元素弹出。为什么因为新元素的下标更新、值又不比它们小只要新元素还在窗口里队尾那些元素永远没机会成为最大值留着纯属占地方。把新元素的下标放入队尾。判断队首下标是否已经滑出窗口左边界如果滑出则弹出队首。我们可以把这个过程想象成“选美大赛的候场队列”新人一上台如果比前面的人都漂亮前面的人就自动退场如果不如前面的人就排在队伍后面等着。但这个队列有一个附加规则一旦有人待的时间超过窗口长度不管多优秀都要离场。function maxSlidingWindow(nums, k) { const result []; const deque []; // 存储下标队首到队尾对应值递减 for (let i 0; i nums.length; i) { // 1. 维护单调性 while (deque.length nums[deque[deque.length - 1]] nums[i]) { deque.pop(); } deque.push(i); // 2. 清理滑出窗口的队首 if (deque[0] i - k) { deque.shift(); } // 3. 窗口形成后才记录结果 if (i k - 1) { result.push(nums[deque[0]]); } } return result; }这份代码有三个地方特别容易写错第一个是循环里的弹出条件用的是而不是。如果改成遇到重复最大值就会保留旧下标在窗口被迫收缩时旧下标的清理时机容易出问题。第二个是清理队首要放在窗口形成判断之前否则当前轮次可能把刚好过期的最大值输出进去。第三个是弹出队首用的是shift()在JavaScript中数组头部的shift操作理论上是O(n)的但考虑到队列长度最多是k同时在真实题目数据下这个开销可以接受。如果追求极致性能可以自己维护head指针实现O(1)出队。3.3 三个边界案例代码里必须一次想清楚边界情况可以说是滑动窗口题的“隐形陷阱”。以下三个案例我建议你拿到题后先在草稿纸上走一遍再写代码第一k等于1。每个窗口只有一个元素最大值就是它本身。单调队列退化为普通队列算法依然正确。第二k等于数组长度。这时只有一个窗口要求的是整个数组的最大值。队首清理逻辑不会触发因为永远没有元素滑出边界。第三数组递减排列比如[5, 4, 3, 2, 1]。这时候队列会“越滚越长”每个新元素都留在队尾因为没有任何元素被弹出。此时队首一直是5和暴力法的结果一致但复杂度仍然是O(n)因为每个元素最多入队一次、出队一次。这三个边界案例覆盖了单调队列代码里的所有分支。如果代码写完之后能逐个跑一遍基本就不会出错了。3.4 复杂度与进一步优化严格分析一下用单调队列解决第41题的复杂度是每个元素最多入队一次、出队一次所以时间上虽然代码里套了while循环总操作次数仍然是O(n)空间上队列最多存储k个下标所以是O(k)。如果你进一步追问“能不能不用维护整个窗口的单调队列”实际上思维可以转向“只求窗口最大值”这个需求本身——我们可以用大顶堆优先队列加上懒删除策略也就是堆顶元素如果不在当前窗口内就延迟弹出。这个方案的时间复杂度同样是O(n)但常数比单调队列大实际运行也慢一些。笔试或面试时优先写单调队列版本即可堆版本可以作为思路备选在讨论环节展示你对多种方案的掌握。4. 第42题数组循环右移三次翻转法的美感在于“零额外空间”第42题的要求是将数组中的元素向右移动k个位置k是非负整数。这道题在LeetCode上的原题是“Rotate Array”。题目很短一眼看上去很简单但它考察的东西却很经典数学规律、边界处理、以及“原地修改”的意识。4.1 最直觉的做法取模映射到新数组最容易想到的方案是新建一个结果数组遍历原数组把每个元素放到(i k) % n的位置上。function rotate(nums, k) { const n nums.length; const result new Array(n); for (let i 0; i n; i) { result[(i k) % n] nums[i]; } for (let i 0; i n; i) { nums[i] result[i]; } }这个解法很容易理解正确性也毫无疑问。但它用了O(n)的额外空间。对很多刷题平台而言这个解法能通过但在面试中面试官往往会追问一句“如果要求空间复杂度O(1)呢你能原地完成吗”4.2 三次翻转法一步步推导为什么可行原地修改最常见的方案是三次翻转法。这个方法第一次看会觉得很神奇但推导起来并不复杂。数组右移k位可以看成两部分后k个元素要跑到数组前面去前n-k个元素要整体往后挪。于是我们把数组分成两段A段前n-k个元素B段后k个元素目标是从[A, B]变成[B, A]。根据数组翻转的基本性质先把整体翻转一次[A, B]会变成[B的逆序, A的逆序]。接着把前半段翻转回来B从逆序变正序再把后半段翻转回来A也恢复正序。结果恰好是[B, A]。三步分别对应代码function rotate(nums, k) { const n nums.length; k k % n; if (n 0 || k 0) return; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } function reverse(nums, left, right) { while (left right) { [nums[left], nums[right]] [nums[right], nums[left]]; left; right--; } }为什么必须先整体翻转再分别翻转两段能不能先分别翻转A、B再整体翻转其实也可以得到的同样是正确的[B, A]。这两种翻转顺序都成立区别只是中间状态不同。实际写代码时选一种固定下来就好不要每次临场换。4.3 边界情况与k取模问题第42题最容易翻车的点其实是k的处理。题目明确说k是非负整数但它没有保证k小于数组长度。如果k比n还大比如n5k7那么右移7位等价于右移7 % 5 2位。因为每移动n位数组会回到原状。所以进入翻转逻辑之前第一件事就是执行k k % n。另一个边界是k恰好等于0或者k是n的整数倍。这种情况下数组不动直接返回。第三次翻转法的三次reverse操作虽然也能跑出正确结果但属于无效功写代码时提前判断一下更干净。还有一个容易忽略的地方是n0。空数组无论怎么旋转都还是空数组取模运算会直接报错所以建议代码最开头就加上n为空的保护。如果你刷题时自测用例没有覆盖空数组真正提交时看到的报错信息通常极其误导人容易让人误以为是翻转逻辑的问题。4.4 如果改成左移怎么写才不容易错左移k位其实等价于右移n - k位。如果题目要求左移你可以在函数入口把k重新计算成k n - (k % n)然后复用右移逻辑。但更直接的方式是调整两次分段翻转的边界整体翻转后先翻转前n-k个再翻转后k个本质上是把A、B两段的分界点换了下位置。我在实际工作中遇到过类似的数组循环滚动场景比如轮播图数据池的滚动那时我习惯在工具函数里同时封装leftRotate和rightRotate两个方法底层共用同一个reverse辅助函数。这样既减少重复代码也不容易在边界上出问题。5. 三道题连刷的实测节奏与事后复盘把这40-42题连续做完一遍之后我记录了实际的时间消耗和遇到的具体问题。这里分享一些个人体会你们照着练的时候可以参考。5.1 我的实测时间记录与途中遇到的问题我自己的练习环境是VS Code Node.js每道题写完之后用命令行跑几个测试用例。三道题的总耗时大约55分钟其中第40题耗时8分钟第42题耗时12分钟第41题耗时35分钟。成绩只能算中等偏上最大的时间黑洞就是第41题的边界调试。第41题第一次写完单调队列版本后我用[1, 3, -1, -3, 5, 3, 6, 7]、k3这个标准用例跑结果是对的但换成[7, 6, 5, 4, 3, 2, 1]、k3时输出完全错乱。调试后发现问题出在弹出队尾的时机我先把新下标push进队列再清理过期队首导致新元素和旧元素在窗口临界处互相干扰。把清理过期队首的步骤提前到push之前之后结果恢复正常。这个坑我认为很多初学者都会遇到可以称为“清理顺序陷阱”。第42题也踩了一个比较隐蔽的坑第一次反转完整体数组之后直接用了k % n作为右半段的起点但没有考虑k0的情况下第二次和第三次reverse会读取非法区间。加上提前return的逻辑之后才算稳妥。5.2 复盘从这三道题里提炼出的通用模板连续刷完三道题后我总结出三个可以迁移到其他题目里的小模板。看到“求满足条件的多数元素”条件里有“超过一半”这种字眼优先往摩尔投票想没有这个条件老老实实上哈希。看到“固定窗口求窗口内最值/统计值”优先想滑动窗口窗口最值优先考虑单调队列窗口求和/计数优先考虑前缀和或双指针。看到“原地调整数组顺序”并且能用简单数学规律描述的优先考虑分段翻转或者多轮原地交换不要急着开新数组。这三个模板不仅适用于这组题在很多数组、字符串类目下能反复复用。你刷完之后也可以自己总结一份“看到什么关键词优先尝试什么思路”的清单比抄别人的笔记有用得多。另外这几天刷题时我还有一个很实际的感受无论第40题的摩尔投票还是第41题的单调队列第一次接触看不懂很正常。看不懂的时候不要背代码拿出纸笔一步一步把数组的每个元素代入走一遍走完一个完整用例基本就通了。这个“手推用例”的习惯比看十遍题解都管用。