准备技术面试刷算法题的时候我遇到过一道看起来特别像生活场景的题给定一个一维花坛数组0表示空位1表示已经种了花要求新种下的花不能和已有花相邻问还能不能种下指定数量的花。题目名字很直观叫“种花问题”。第一次做它的时候我以为要老老实实模拟种花过程做完了才发现这题真正考的是贪心思维如何在长度上万的花坛数组里快速判断还能塞下几朵花。这道题在各类在线评测平台上都有收录属于“面试高频且代码量不大”的典型题。你如果刚开始刷贪心拿它当入门非常合适如果处在面试冲刺期它也经常被当作二面里“先讲思路、再做优化”的热身题。适合谁看呢我认为是两类人一类是刚学会数组遍历、想找一道能“练透边界处理”的初级题的人另一类是已经能AC但想把“为什么能贪心”讲清楚、应付面试官追问的人。这篇内容我会从题目本质拆起给出三种解法、完整边界条件分析和面试表达技巧最后附一组我踩过的坑和自查清单。1. 题目本质一个被包装成种花的数组遍历问题1.1 题目到底在说什么先还原完整题面。有一个长度为 m 的整数数组 flowerbed每个元素只有两种取值0 表示这个位置是空的可以种花1 表示这个位置已经种了花。种新花时有硬性约束任意两朵花不能种在相邻位置上。也就是说最终数组里不能出现连续的两个 1。题目保证输入数据本身合法也就是原始数组里已经存在的 1 不会相邻。现在给你一个整数 n让你判断还能不能在这个花坛里再种下 n 朵花。举一个最典型的样例flowerbed [1,0,0,0,1]n 1答案是 true因为可以把新花种在中间那个 0 的位置得到 [1,0,1,0,1]但如果 n 2答案就是 false因为即使把两个 0 都利用起来中间只有连续三个 0受两边已有花的限制最多只能再种 1 朵。从抽象的角度看这道题本质是在一个存在若干“禁用点”的一维数组里选择尽可能多的互不相邻的空位置。数组结构、种花规则都是包装层内核是“不相邻选点”的组合问题。理解了这一层后面很多变体题你都能一眼看穿。1.2 为什么这道题适合练贪心原因有三点。第一它不需要复杂的数据结构。你只需要一个数组、一个计数器、一次遍历连哈希表都用不上。这降低了理解成本很适合拿来建立“贪心策略”的直觉。第二它的“最优子结构”非常明显。从左到右处理花坛时每处理完一段剩余部分就是一个更短的花坛子问题。你不需要回头看已经处理完的区域只需要关心当前位置和下一两个位置这种局部决策驱动的结构就是贪心算法的典型土壤。第三它有一个天然的开销极低的判定标准能种就种。很多贪心题需要复杂的排序或者堆来辅助而这题根本不需要因为数组顺序已经给定你只要决定“这朵花要不要种在这里”。我自己刷题时的一个判断标准是如果一道题能在 20 分钟内讲清楚“贪心为什么正确”它就是一道好的入门贪心题。种花问题完全满足这个标准。1.3 输入规模与约束的潜台词很多人做题不先看数据范围这习惯要改。花坛长度 m 通常在 1 到 10^4 这个量级元素只有 0 和 1n 的范围一般是 0 到 10^4。这意味着你的最优解至少得是 O(n) 级别的遍历O(n²) 的暴力大概率会超时空间上O(1) 是你应该追求的目标n 可能为 0这是一个经常被忽略但白送分的边界条件m 可能为 1也就是只有一个格子的花坛这时候判断逻辑要格外小心。另外题目保证原始数组里没有相邻的 1这一点很重要。如果面试官突然改口说“输入可能非法”那就是另外一个防御性编程的问题了面试时可以主动提一句。2. 三种解法从暴力到贪心的完整推导2.1 暴力模拟先把规则跑通再说第一次碰到这题大多数人会这么想既然要判断能不能种 n 朵那就真的去种一遍数一数最多能种多少朵。朴素写法很直接从左到右遍历每个位置如果当前位置是 0并且左边不是 1、右边也不是 1那就可以种于是把这个位置改成 1计数器加一。def can_place_flowers_naive(flowerbed, n): count 0 length len(flowerbed) for i in range(length): if flowerbed[i] 0: left_empty (i 0) or (flowerbed[i - 1] 0) right_empty (i length - 1) or (flowerbed[i 1] 0) if left_empty and right_empty: flowerbed[i] 1 count 1 return count n这个写法本身没有错误时间复杂度也是 O(n)。但它有一个不容易察觉的问题种完花之后代码不会主动跳过下一格下次循环仍然会检查已经种下花的右侧相邻格。虽然检查结果依然正确因为种了花之后这个格子会变成 1右侧格子在下一轮判断时左边不空不会重复种但这种做法实际上多做了一些无用判断。面试时写出这个版本可以作为“正确性优先”的起点但不要停在这里。下一步要想的是能不能利用规则本身减少扫描次数2.2 区间统计法从“数连续0”理解种花上限如果换一个角度把花坛看成由若干个“连续 0 段”拼接起来的结构问题会变得更数学化。每一段连续 0 的两边是边界或者 1这一段的长度决定了它的种花上限。具体公式分三种情况。中间段两边都是 1连续 0 的长度为 k那么最多能种 ((k-1)//2) 朵。比如 [1,0,0,0,1]中间 k3最多种 1 朵[1,0,0,0,0,0,1]中间 k5最多种 2 朵。首尾段只有一边是 1另一边是数组边界连续 0 的长度为 k最多能种 (k//2) 朵。比如开头是 [0,0,0,1]k3可以种在位置 0共 1 朵开头是 [0,0,0,0,1]k4可以种在位置 0 和 2共 2 朵。全零段整个花坛全是 0长度为 k最多能种 ((k1)//2) 朵。比如全零长度 5可以种在位置 0、2、4共 3 朵。这个统计法可以写成代码但需要小心首尾和全零的区分容易漏掉特殊情况。我一般都是把它当成推导工具用来快速心算出某个花坛的“最大容量”而不太推荐作为面试时的主写版本。因为面试现场写公式不如写一个逻辑直白、边界统一的遍历版本来得快。不过这个公式有一个很实用的价值它可以帮你快速估算上限。比如面试官追问“如果 n 特别大呢”你可以在遍历前先用公式判断一下整体容量上限一旦 n 超过上限就直接返回 false省掉一次完整遍历。2.3 标准贪心O(n)时间O(1)空间的跳格遍历接下来是这道题最推荐的解法我称它为“跳格遍历法”。核心逻辑就一句话从左到右看遇到已种花的位置它的下一格因为相邻规则一定不能种直接跳过两格遇到空格如果左右都空就种上种完以后下一格也一定不能种继续跳过两格只有左右有一边不空时才老老实实挪动一格。def can_place_flowers(flowerbed, n): count 0 i 0 m len(flowerbed) while i m: if flowerbed[i] 1: i 2 continue left_empty (i 0) or (flowerbed[i - 1] 0) right_empty (i m - 1) or (flowerbed[i 1] 0) if left_empty and right_empty: flowerbed[i] 1 count 1 if count n: return True i 2 else: i 1 return count n我特别想强调这个 i 2 的设计。它不只是常数优化而是把贪心策略真正落实到了遍历节奏上。每当你在位置 i 种下一朵花位置 i1 无论原来是 0 还是 1都已经丧失了种花资格所以没必要再访问它。同理遇到原始为 1 的位置它的右侧邻居也必然丧失资格。这个“跳过两格”的动作是合法且安全的。那为什么左右有一边不空时只能 i 1因为当前位置不能种但下一个位置仍然可能种得下。例如花坛是 [1,0,0]遍历到 i1 时左边是 1不能种但 i2 是空位且它是末端右侧自然为空所以 i2 可以种。如果这里也莽撞地 i 2就会漏掉这朵花。这个版本是真正的标准答案时间 O(n)空间 O(1)只做必要的检查。我自己面试时首推这个版本。2.4 补零法让边界判断不再头疼跳格法虽然标准但对新手有一个门槛i0 和 im-1 时的左右边界判断容易写错。一个非常讨巧的替代方案是“补零法”思路是在原数组首尾各补一个 0这样所有真实位置都有了左右邻居遍历时不再需要特殊处理边界。def can_place_flowers_with_padding(flowerbed, n): if n 0: return True beds [0] flowerbed[:] [0] count 0 length len(beds) for i in range(1, length - 1): if beds[i - 1] 0 and beds[i] 0 and beds[i 1] 0: beds[i] 1 count 1 if count n: return True return count n这个写法的好处是判断条件非常对称只要连续三个位置都是 0中间那个位置就可以种花。代码一眼就能看懂边界错误概率几乎降到零。代价是复制数组会带来 O(n) 的额外空间。如果你面试时先写了补零版面试官问能不能优化空间正好可以顺势切到跳格版。这也是一种非常好的面试节奏先写稳定版本保证正确再展示你理解空间优化。我还测试过这个补零法在实际运行中的表现。因为 Python 的列表拼接和遍历本身效率不低在 10^4 的长度下两种写法的时间差异完全感知不到。所以如果你在笔试平台只追求 AC补零法完全够用但如果面试现场要求手写最优解跳格法才是正餐。3. 边界条件与隐藏坑点全梳理3.1 数组开头和结尾最容易越界的两处种花问题的边界坑十个人里有八个会踩在数组两端。当你检查位置 i 是否能种花时需要看 i-1 和 i1 两个邻居。如果 i0i-1 越界如果 i数组末尾i1 越界。很多新手第一次写的时候直接判断 flowerbed[i-1] 0然后收到一个 IndexError瞬间心态崩掉。处理方式一共有三种我按推荐程度排序。第一种是用条件表达式也就是代码里最常见的写法left_empty (i 0) or (flowerbed[i - 1] 0)。这里利用了 Python 短路求值i0 时后面不会执行所以不会越界。右侧同理。第二种是补零法。把数组扩展成 [0] flowerbed [0]然后遍历中间部分。真实位置的左右邻居永远是存在的彻底消灭越界分支。第三种是在循环开始前手动处理两端比如分别判断位置 0 和位置末尾代码会变得冗长我不推荐。这里有一个我踩过的坑(i 0) or (flowerbed[i - 1] 0)这句话的顺序很重要。如果把条件写成(flowerbed[i - 1] 0) or (i 0)当 i0 时依然会先执行越界访问照样报错。短路逻辑必须把越界判断放在前面。3.2 全零数组与长度为1的特殊场景全零数组是个容易被公式搞混的场景。连续 5 个 0很多人直觉以为能种 3 朵因为位置 0、2、4 都可以种但连续 4 个 0 就只能种 2 朵因为位置 0 和 2 可以种位置 3 没法种。这个规律用公式表示就是 ((k1)//2)注意它是向上取整的变体。你可以自己手推几个小数组验证全零长度 1、2、3、4、5 的可种数量分别是 1、1、2、2、3。长度为 1 的数组更特殊。flowerbed [0] 时这唯一一个空格可以种 1 朵flowerbed [1] 时任何新花都不能再种。跳格法处理 [0] 时i0 满足左右皆空种下后 i 2循环退出处理 [1] 时i 2循环退出。逻辑没问题但如果你用补零法[0] 会变成 [0,0,0]遍历 i1 时三连 0正常种下 1 朵也正确。怕就怕在脑内模拟反面情况时把 [0,0] 误判为能种 2 朵。实际上 [0,0] 种了位置 0 之后位置 1 就废了最多 1 朵。这类小数组建议直接写进测试用例靠记忆不靠谱。3.3 提前返回与不可修改数组的进阶需求两个容易被追问的点。第一个是 n0 要不要特殊处理。我的建议是直接返回 True因为 n0 意味着不需要种任何花无论花坛长什么样答案都是 yes。补零版里如果不提前返回遍历虽然也能得出 count0 恒为 true但会白白走一遍循环。提前返回既是优化也体现了你对边界条件的敏感度。第二个是“如果面试官不允许修改原数组怎么办”。跳格法里我直接写flowerbed[i] 1这修改了输入。有些面试场景会明确要求“不得修改输入数据”。此时可以用一个布尔变量记录上一格是否处于“刚种完花”的状态替代对数组的写操作def can_place_flowers_no_modify(flowerbed, n): if n 0: return True count 0 prev_planted False for i in range(len(flowerbed)): if flowerbed[i] 1: prev_planted True continue left_empty not prev_planted right_empty (i len(flowerbed) - 1) or (flowerbed[i 1] 0) if left_empty and right_empty: count 1 prev_planted True if count n: return True else: prev_planted False return count n这个版本的思路是虽然不能改数组但我可以用一个变量记住“上一格到底有没有花”这个信息足以支撑左侧判断。右边的判断仍然需要看原数组的下一格因为没有别的信息源。总体上时间 O(n)、空间 O(1)同时保证不修改输入。面试时能写出这个版本会加分不少。4. 面试里的算法表达与延伸思考4.1 为什么贪心是对的一个三句话证明很多读者会问跳格法里“能种就种”怎么保证这样得到的数量就是最大值万一某个位置不种反而能腾出空间种更多朵呢这个问题如果答不好面试官会判定你对贪心算法一知半解。我准备了一个三句话版本亲测在面试中非常好用。第一句从左到右处理时当前这个可种位置是剩余花坛中“最靠左”的候选点任何最优方案如果想在它右侧开始种都不可能比从它这里开始种更靠前。第二句如果最优解里它左侧某些位置也要种花那么这些位置在贪心策略处理时也该已经种下了和当前点的顺序不冲突。第三句种下当前这朵花之后唯一被禁用的是紧挨着的下一格如果不种当前这朵下一格或下下一格可能能种但最多也只能种出一朵并不能带来“种得更多”的收益所以局部最优不会损害全局最优。简单来说在空位充足时早种不亏晚种不多在空位紧张时早种抢占的是本来就冗余的位置也不会挤压远处的空间。这套直觉配合反证法就能构成一个完整的贪心正确性论证。我不建议你去背诵严格数学证明面试官更想听到的是你能用自己的话把“早种不亏”这件事讲明白。4.2 复杂度分析的两种视角种花问题的复杂度分析看起来很简单但我见过不少候选人在这里翻车。时间复杂度的直观结论是 O(n)因为无论跳格版还是补零版每个位置最多被访问常数次。跳格版里有些位置会跳过两次但整体循环次数仍然是 m 的线性函数不会出现 O(n²) 的问题。空间复杂度则要看版本。跳格版是 O(1)补零版是 O(n)因为复制了一个新数组。面试官如果追问“为什么补零版翻倍了”你要能答出它为了统一边界判断而牺牲了额外空间。实际工程里这种取舍很常见代码清晰度优先还是内存占用优先要看场景。算法题里通常推荐先给出 O(1) 空间版本但如果为了快速写出 bug-free 代码补零版也完全可接受。还有一个值得提的优化点遍历过程中一旦 count 达到 n可以立刻返回 true不需要继续扫描。这个提前终止在很多测试用例里能省掉近一半的时间。我在代码里已经加了这个判断面试时也别忘了提一句。4.3 常见变体环形花坛、距离约束延长与反向问题如果面试官觉得这题太简单通常会抛出一两个变体来压深度。我整理过几个高频变体每个都能单独聊五分钟。环形花坛变体花坛首尾相接位置 0 和位置 m-1 也算相邻。这个问题最朴素的处理方式是枚举两个基本情况在位置 0 种花或者不在位置 0 种花然后在剩余的线性结构上跑原来的贪心。因为环形只是在首尾之间额外加了一条约束所以只要固定住首尾状态问题就退化成了线性情况。距离延长变体要求任意两朵花之间至少空两格而不是一格。此时判断条件要从“左右相邻为 0”改成“左边隔一个位置为 0右边隔一个位置为 0”跳格距离也相应变成每次跳三格。你会发现解法骨架完全没变变的只是常数。这正是这类题的价值它训练的是“规则变化的敏感度”。反向问题变体已知花坛长度和要种的花的数量问至少需要多长的花坛。这个本质上就是把全零公式 ((k1)//2) 反解成 k 的范围属于高中数学级别的推导但放到面试里能考察你对公式的理解深度。遇到变体题不必慌先判断它改变了哪个约束条件再想这个约束条件怎么映射到原题的数组遍历上。几乎所有变体都能还原成“带额外约束的线性扫描”。5. 输入样例与自查清单5.1 一组值得手推的测试用例我整理了一组我自己刷题时常跑的用例覆盖了大部分边界情况。你写完代码后建议把下面这张表手动推一遍再交给在线测评。花坛数组目标 n预期结果说明[1,0,0,0,1]1true经典样例种在中间[1,0,0,0,1]2false中间最多再塞 1 朵[0,1,0,1,0]1false每个 0 都被两侧的 1 夹住[0,0,0,0,0]3true全零数组种 0、2、4[0,0,0,0,0]4false全零长度 5 上限是 3 朵[0,0,1,0,0]2true两头各能种 1 朵[1]0truen 为 0 恒真[0]1true单空位可种 1 朵[1,0]1false唯一空位与已有花相邻[0,0]1true种位置 0 即可[0,0]2false两个连续 0 最多 1 朵手动推这些用例最大的价值是能让你对“连续 0 段到底能种几朵”形成肌肉记忆。我第一次刷的时候连续四次栽在 [0,1,0,1,0] 这种看似空位很多、实际一朵都种不下的用例上。后来养成了“先数段、再套公式、最后写代码”的习惯这类问题基本不再犯错。5.2 同类题单与刷题建议种花问题在贪心题单里属于“直觉型题目”但它和几个常见题型有很强的关联。比如跳跃类问题核心都是“在某个位置做决策后后续可到达范围发生变化”区间类问题关注的是“局部最优决策是否影响后续区间”。刷题时我建议把种花问题当作一个锚点用来串联其他贪心基础题分发饼干、跳跃游戏、无重叠区间、加油站等。它们共享同一个思考框架每一步做出局部最优选择并用反证法或替换法证明不会破坏全局最优。如果你想把这个题刷透我的建议是写三个版本补零版、跳格版、不可修改输入版。每个版本写完之后都追加两个问题这个版本的空间复杂度是多少如果去掉提前返回耗时会不会有感知差异能把这三个版本和两个问题全部说清楚这道题才算真正吃透而不是仅仅 AC 一次。我自己在面试和带新人时最喜欢的训练方式是让对方在白板上先讲思路再写补零版最后口头改写成跳格版。整个过程通常控制在八分钟以内。它能快速判断一个人是背了模板还是真的理解了这个规则。结尾我最早做种花问题时也纠结过要不要用动态规划后来才发现这道题考察的就是你能不能把一个简单的决策规则讲清楚。种花问题难的地方其实不在写代码而在你敢不敢在“能种就种”面前停下来认真证明它是对的。把这个证明想透之后你会发现自己对贪心算法的理解会有一个明显的台阶式提升。最后分享一个小技巧刷完题之后把这道题的所有边界用例截图存进自己的笔记里隔一周再写一次。不要看之前的代码看你能不能一次写出 bug-free 的跳格版。如果能说明这类“不相邻选择”的题你已经真正拿下了。后续遇到环形变体、间隔延长变体你也能快速迁移思路而不是重新从头开始想。