LeetCode 1437：高效判断数组中1是否相隔k个元素

前两天在题库里刷到一道有意思的简单题编号1437题目叫“是否所有 1 都至少相隔 k 个元素”。题面一句话就能讲完给一个只含 0 和 1 的数组再给一个整数 k问数组中任意两个相邻出现的 1中间是否都隔了至少 k 个元素。提交之后看到耗时击败了 100% 的提交不过这个“100%”其实不值得兴奋——真正值得聊的是为什么这个解法能做到 O(n) 时间、O(1) 空间以及这道题的边界为什么比很多人想象中更容易踩坑。这篇就当一次完整的拆解记录从题面翻译、三种解法对比、代码细节到变体扩展一次说清楚。1. 题面拆解先搞清楚“至少相隔k个元素”到底在说什么1.1 把中文题面翻译成数学条件题目说的是“至少相隔 k 个元素”这里的“相隔”指的是两个 1 之间夹着多少个元素也就是 0 的个数。举个例子数组[1, 0, 0, 0, 1]中两个 1 的下标分别是 0 和 4中间夹着 3 个 0那么它们就“相隔 3 个元素”。用下标来表达会更精确设两个相邻 1 的下标为i和j它们中间元素的数量是j - i - 1。要求这个数量大于等于k也就是j - i - 1 k两边整理一下j - i k这个等价变换是整个题目的核心。很多人写错代码根源就是把j - i - 1 k和j - i k混为一谈差了一个 1结果条件方向完全不对。为什么只需要检查“相邻”的 1因为所有 1 按下标排序之后任意两个 1 之间的距离一定大于等于它们之间某一段相邻 1 的距离。换句话说只要每一对相邻的 1 都满足距离约束那么跨多个 1 的那对也必然满足反过来只要有一对相邻 1 不满足整个数组就不满足。所以扫描数组时我们只需要记住“上一个 1 出现在哪里”完全没有必要维护所有 1 的位置列表。用一个生活类比来说就像排队时要求队伍里所有“1 号顾客”之间至少隔 k 个人其他都是“0 号顾客”。你不需要记住所有 1 号顾客的位置只需要盯着最近一个 1 号顾客每次遇到新的 1 号顾客时确认中间人数是否够即可。1.2 三个容易踩的理解误区第一个误区是把“相隔 k 个元素”理解成“相隔 k 个下标位置”。这是我在评论区看到过很多次的错误。两个元素相差 1 个下标其实是紧挨着的中间 0 个元素相差 2 个下标中间才有 1 个元素。所以“相隔 k 个元素”对应的是下标差大于 k而不是大于等于 k。第二个误区是有人会把问题理解成“检查数组里是否存在两个相邻位置都为 1”。实际上题目要求的是“相邻出现的两个 1”中间可以隔任意多个 0。比如[1, 0, 1]里的两个 1 是相邻出现的只不过中间隔了一个 0。如果只检查数组位置上是否相邻那这道题就完全变味了。第三个误区藏在 k 0 的场景里。k 0 表示两个 1 之间至少相隔 0 个元素那么[1, 1]其实是符合条件的因为两个 1 中间有 0 个元素0 0 成立。不少人会凭直觉觉得“相隔 0 个元素意味着必须有不同的位置”其实两个 1 只要下标不同它们中间就至少有 0 个元素所以 k 0 时任何数组都直接返回 true。这个结论有点反直觉后面我会在边界用例表里专门列出来。1.3 这道题放在面试里到底想考察什么作为一道简单题它不考复杂算法不考数据结构但它精确地踩中了三个面试官常考的点把自然语言翻译成数学条件的能力、边界条件的设计能力、以及空间使用的习惯。能把j - i - 1 k等价成j - i k说明你具备“先把条件写清楚再写代码”的意识。能想到只维护一个prev变量而不是收集所有 1 的下标说明你有压缩空间的本能。能主动列出 k 0、数组全 0、只有一个 1 这些用例说明你知道代码的坑往往不在主路径上。简单题的意义从来不是“会做”而是能不能做到严密、简洁、可解释。2. 三种解法横向对比先别急着写最优解2.1 解法一先收集所有 1 的下标再两两比较最直观的思路是第一遍遍历数组把所有 1 的下标记到一个列表里第二遍遍历这个列表检查相邻两个下标之差是否大于 k。def k_length_apart(nums, k): ones [i for i, x in enumerate(nums) if x 1] for a, b in zip(ones, ones[1:]): if b - a k: return False return True这个解法本身没有逻辑错误而且代码很直白适合作为“第一版保底方案”在面试中先抛出来。但它的缺点是明显的需要 O(m) 的额外空间m 是 1 的个数在极端情况下比如数组全是 1这个列表的大小和原数组一样大。另一个隐蔽的缺点是“无法提前返回”列表推导式必须先完整遍历数组哪怕第一个 1 和第二个 1 之间的距离已经违规也得等整个数组扫描完才能开始判断。不过作为参照实现这个方案非常有价值。后面我会提到用它来和最优方案做输出对拍是排查条件写反的利器。2.2 解法二只记住上一个 1 的位置这是本题的标准答案。核心思想是我们只需要关心“上一个 1 在哪里”因为每次遇到一个新的 1唯一需要比较的对象就是它前面最近的那个 1。算法流程很简单用一个变量prev记录上一个 1 的下标初始值设为 -1表示“还没遇到过 1”。遍历数组遇到 1 时如果prev不是 -1说明这不是第一个 1检查i - prev是否小于等于 k如果是直接返回 false更新prev i。遍历结束返回 true。这个方案的时间是 O(n)空间是 O(1)并且一旦发现违规可以立刻返回不需要扫描完整个数组。它充分利用了题目的“相邻 1 距离”的性质把状态压缩到了极致。2.3 解法三固定宽度滑动窗口还有一类思路是维护一个宽度为 k 1 的窗口窗口内如果出现两个 1 就说明距离太近。这个思路在“是否存在窗口内重复元素”这类问题里很常见但放到这道题里有点杀鸡用牛刀。滑动窗口需要维护窗口内 1 的计数窗口滑动时左侧出去一个元素要判断是否是 1右侧进来一个元素也要判断。代码写起来比单指针方案复杂不少而且窗口初始化的开销取决于 k 的大小。当 k 很小时还好k 接近 n 时窗口本身就可能覆盖大半个数组。这个方案能帮你理解“滑动窗口”这类更复杂题目的思路但在这道题里并不推荐。考试和面试都讲究用最简单有效的工具解决当前问题单指针方案已经是这个问题的“最短路径”。2.4 三种方案的对比表与结论方案时间复杂度空间复杂度能提前返回推荐度收集下标再比较O(n)O(m)m 为 1 的个数否适合保底和调试参照单指针记录上一个 1O(n)O(1)是标准答案滑动窗口计数O(n)O(1)是代码复杂不推荐结论很清楚单指针方案在时间、空间、可读性三个维度上都最优。面试时可以直接从收集下标的朴素方案讲起然后过渡到单指针方案展示你“能想到优化”的过程。3. 核心代码实现与关键细节3.1 Python 逐行注释版我用 Python 写一版可以直接跑的代码def kLengthApart(nums, k): prev -1 # 上一个 1 的下标-1 表示还没有遇到过 1 for i, x in enumerate(nums): if x 1: # 如果之前出现过 1且当前下标与上个 1 的距离 k则不满足 if prev ! -1 and i - prev k: return False prev i return True逐行解释一下prev -1这里用 -1 做哨兵而不是用 0。如果用 0 初始化那么第一个 1 出现在下标 1 时i - prev 1如果 k 0就会被误判为违规。用 -1 配合prev ! -1判断可以完美避开这个问题。i - prev k这是整个代码最关键的一行。注意是小于等于不是小于。因为条件是j - i - 1 k不满足的情况就是j - i - 1 k也就是j - i k。多一个等号少一个等号结果天差地别。先判断再更新一定是先拿当前 1 和上一个 1 比较然后再把prev更新为当前下标。顺序反了就会漏掉当前这一个 1 的检查。这套代码不管数组里有多少个 01 什么时候出现都能正确工作。3.2 C 面试手撕版与哨兵变量的坑C 版本同样简洁bool kLengthApart(vectorint nums, int k) { int prev -1; for (int i 0; i (int)nums.size(); i) { if (nums[i] 1) { if (prev ! -1 i - prev k) { return false; } prev i; } } return true; }这里有一个值得单独拎出来说的坑有人为了省掉prev ! -1的判断会把prev初始化为-k - 1。这样第一个 1 出现时i - prev k 1天然满足不需要特判。这个技巧本身没问题Python 里完全可以用因为 Python 的整数没有溢出概念。但 C 里有风险如果 k 接近INT_MAX-k - 1本身就可能触发溢出或者变成不可预期的值。所以 C 里我建议老老实实用prev -1加一个判断不要玩这种哨兵技巧。面试时宁可多写一行判断也不要在一个看似巧妙的初始化上翻车。顺便给一个 Go 版本思路一模一样func kLengthApart(nums []int, k int) bool { prev : -1 for i, x : range nums { if x 1 { if prev ! -1 i-prev k { return false } prev i } } return true }三个语言版本核心逻辑完全一致面试时不管你用什么语言照着这个骨架写都不会错。3.3 边界用例清单我列一个每次写完后都要过一遍的边界用例表比盲跑测试数据有用得多用例k预期结果原因[]任意true没有 1 需要检查[1]任意true只有一个 1[0, 0, 0]5true没有 1[1, 1]0true两个 1 中间有 0 个元素0 0[1, 1]1false两个 1 中间有 0 个元素0 1[1, 0, 1]1true中间有 1 个元素1 1[1, 0, 1]2false中间有 1 个元素1 2[1, 0, 0, 0, 1, 0, 0, 1]2true两段距离分别满足[1, 0, 0, 0, 1, 0, 0, 1]3false第二段中间只有 2 个元素[1, 0, 0, 0, 0, 1]4true中间 4 个元素恰好等于 k这里面最值得记住的是[1, 1]和 k 0 那行。我在实际刷题过程中发现十个人里有五个人会把 k 0 的情况想反剩下五个人里还有两三个会把条件里的等号写错。这两行用例能帮你快速证明代码逻辑与题目定义一致。3.4 “耗时击败100%”到底意味着什么回到标题里的“耗时100”。提交页面上显示“击败 100% 的提交”这个数字其实不需要过度解读。LeetCode 的耗时排名会受到测试机负载、语言版本、输入数据分布等多个因素影响同一份代码多提交几次百分比都可能浮动。对这道题来说O(n) 就是理论下限要判断所有 1 的位置关系至少得把每个元素看一遍不可能低于线性复杂度。所以只要你的代码是单次遍历就已经站在最优复杂度的起跑线上了。那“击败100%”说明什么呢说明你的代码在常数层面也没有浪费没有额外分配大数组、没有做多余的内层循环、找到违规立即返回。但我不建议为了追求这个百分比去写一些看起来炫技的代码。比如把遍历改成位运算技巧或者用哨兵数组把循环体压缩成一行。代码是给人读的面试官首先看的是思路清晰度。一个只用三个变量、一眼能看懂的解法比一个跑得快但需要盯半天的奇技淫巧要值钱得多。4. 变体与扩展换一个问法你还认得它吗4.1 改成流式输入喂一个元素判断一次如果数组不是一次性给出的而是以数据流的形式不断到达每来一个元素都要立刻判断“到目前为止是否满足条件”这套解法依然成立。因为单指针方案的状态只依赖一个prev变量不需要回头访问数组历史元素。每次新元素到达时只需要做一次判断再决定是否更新prev整个过程是严格 O(1) 的。这是“流式友好”的典型特征。相比之下收集下标方案在流式场景下就非常尴尬你不知道后面还会不会来 1也没办法提前结束必须把整个数据流全部接收完才能开始比较。这就是为什么“只维护最小状态”不仅是为了省内存更是为了应对更灵活的场景。4.2 改成环形数组首尾相接怎么处理如果把数组首尾相接形成一个环那么“最后一个 1”和“第一个 1”也变成了相邻关系需要额外检查。处理方法也不复杂在普通遍历过程中记录下第一个 1 的下标first和最后一个 1 的下标last。遍历结束后额外检查一下环上的这一对从last沿正向走到first中间夹的元素数量是n - last first - 1要求它大于等于 k。这个问题有一个常见误区有人想直接把数组复制一份拼接起来再跑原算法。那样做虽然能覆盖首尾衔接的情况但会在拼接处产生一对“额外的相同元素”导致误判。正确做法是单独处理这一对相邻关系而不是粗暴拼接数据。这种“先拆环再补最后一刀”的思路在很多环形数组题目里是通用的。4.3 把“1”换成任意值从单点变成多点如果题目改一下给定一个整数数组检查任意两个相同的值是否至少相隔 k 个元素。此时就不能只用单个prev变量了因为可能有多种取值每一种值都需要记录自己最近一次出现的位置。解法是用一个哈希表key 是元素值value 是该值最近一次出现的下标def all_values_k_apart(nums, k): last {} for i, x in enumerate(nums): if x in last and i - last[x] k: return False last[x] i return True复杂度是 O(n) 时间、O(不同值个数) 空间。这就是“单指针记录上一个位置”的通用化版本也是很多“窗口内重复元素”类题目的底层套路。从这道简单题的单个prev变量升级到哈希表维护多个“prev”逻辑上的连续性是相当自然的。4.4 和几道经典题的“血缘关系”这类“检查元素间距”的问题在题库里其实是一个家族。比如“种花问题”本质是检查已经种下的花之间距离是否至少为 2只是换成“还能不能继续种”的问法再比如“存在重复元素 II”本质是检查是否存在下标距离不超过 k 的相同值代码和上面哈希表版本只差一个不等号方向。把这个家族放在一起看你会发现它们都共享同一个最小状态上一个目标值出现的位置。区别无非是目标值是一个还是多个距离条件是大于还是小于。把这道 1437 题吃透等于给这个家族打了一个地基。5. 实际调试中的问题排查与技巧实录5.1 常见错误速查表我在自己写这道题以及帮别人 review 代码时见到的高频错误基本集中在下面几个点错误现象可能原因修复方式第一个 1 就被判为 falseprev初始化为 0 或数组下标范围内的值prev初始化为 -1并配合prev ! -1判断k 0 时返回 false条件错写成i - prev k条件应该是i - prev k数组全 0 时返回 false在遍历过程中误把“没遇到 1”当作违规没有 1 时直接返回 true返回值整体反了没有先明确“不满足条件”的定义先写出数学式j - i - 1 k再推导违规条件收集下标方案里比较错了对象用了ones[i]和ones[i 1]但循环范围越界用zip(ones, ones[1:])或从 1 开始遍历以为 k 很大时不需要检查忽略了距离条件只和 1 的位置有关和 k 大小无直接关系遇到 1 就必须检查i - prev与k的关系这些错误绝大多数不是“不会做”而是“转换条件时差了一个等号”。所以我的习惯是先不写代码在纸上把j - i - 1 k和它的否定形式j - i k写出来再开始动键盘。5.2 我每次提交前都会跑的自测用例除了上面表格里的边界用例我还会在本地跑一组随机测试生成几十万个长度在 1 到 20 之间的随机 0/1 数组随机 k然后用两个方案做对拍——一个是我写的单指针最优版另一个是收集下标的朴素版。两个输出必须完全一致只要出现一处不一致就说明某一个版本的条件方向有问题。这个“对拍”的习惯帮我在很多简单题上省下了反复提交的时间。因为 LeetCode 提交失败一次心态和状态都会受一点影响而在本地把逻辑验证死提交就是一次过。5.3 调试策略从暴力解到最优解的双跑验证具体操作分三步第一步先写收集下标版本。这个版本的逻辑最贴近自然语言不容易写错适合作为“需求文档”式的参照实现。第二步再写单指针版本。写的时候注意三个易错点prev初始值、不等号方向、更新prev的时机。第三步用一个脚本随机生成测试数据把两个版本跑同一批输入结果不一致就打印出数组、k 和两个函数的返回值。这一步能快速定位到底是哪个条件写反了而不是靠肉眼一行行盯代码。这个方法尤其适合面试前的集中刷题阶段。简单题一天刷十几道靠对拍可以保证每一道都“真正写对”而不是“自我感觉写对”。6. 把“间距约束”抽成通用模板6.1 五行的套路模板把整道题剥到最后核心模板其实只有五行last 哨兵值如 -1 for i in range(n): if nums[i] 目标值: if last 有效 and i - last k: return False last i return True这个模板可以套到几乎所有“按出现顺序检查相邻目标值间距”的问题里。使用时只需要回答三个问题目标值是什么决定nums[i] target的写法。需要记录几个“上一个位置”如果只有一个目标值一个变量够用如果有多个目标值换成哈希表。违规条件是什么距离小于等于 k 还是大于等于 k取决于题目要求的是“至少相隔”还是“至多相隔”。把这三个问题想清楚代码自然就出来了。6.2 模板升级从单个目标值到多个目标值当问题从“检查所有 1”变成“检查所有相同值”时模板只改两处把单个last变量换成哈希表把查找目标值的条件改成“当前值是否已经在哈希表里”。空间复杂度从 O(1) 变成 O(不同值个数)换取的是能处理任意数组的通用性。这个升级方向也是面试官常用来加码的方向。一道简单题从“单指针扫一遍”聊到“哈希表维护多个最近位置”再聊到“流式输入怎么办”其实已经把数组类问题的几个核心考点都覆盖了。我自己在复习时习惯把每道简单题都往这个方向推一遍先问自己“状态能不能再压缩”再问“目标值能不能泛化”最后问“输入方式能不能变”。这三个问题问完一道题的理解深度会明显不一样。这道 1437 题本身确实简单但把它拆开看里面藏着的边界条件处理、数学等价转换、最小状态维护、变体泛化能力恰好是刷算法题最该练的那几块基本功。希望这篇记录能让你的思路像我一样清晰——哪怕下次在题库里遇到的是它的各种变体也能一眼认出这个“记住上一个位置”的老朋友。