种花问题是我在题库和面试里见过很多次的经典贪心题。题目会给你一个花坛用一个整数数组表示1代表已经种了花0代表空位规则是任意两朵花不能种在相邻位置。现在你手里有n棵花苗要判断能不能全部种下去。听起来很像“数一数空位够不够”的小学算术但真正动手写就会意识到边界怎么处理、能不能重复计数、为什么从左往右扫一遍就能得到最优解每一处都藏着坑。这篇文章我会从题目拆解、贪心原理、代码实现、变体扩展到调试经验完整过一遍适合正在准备算法面试的人也适合想看明白贪心算法到底在贪什么的新手。如果你只是急着过用例可以直接跳到第三章抄代码。但如果你愿意花十分钟理解“能种就种”为什么成立以后再遇到类似的区间冲突题会轻松很多。顺便说一句这道题不需要任何数据结构基础数组、循环、布尔判断就够所以也是新手入门贪心的绝佳样本。我下面写的所有代码都以“不违反相邻规则”为前提假设输入里已经种下的花本身是合法的这样我们可以把注意力完全放在“如何再塞n朵花”上。1. 题目到底在考什么1.1 问题描述再翻译一遍把题目里的花坛当成一排连续的格子。数组flowerbed的长度为m每个位置只能是0或1。0代表这个格子空着1代表已经种了花。现在要把n朵新花种进去规则是任意两朵花不能相邻也就是说如果某个位置种了花它左边和右边紧挨着的位置都不能再种。最后要返回一个布尔值表示能不能做到。举个例子flowerbed [1,0,0,0,1]n1时可以在中间三个0的任意一个位置种下一朵返回true。n2时三个连续空位只能容纳一朵因为种在中间位置后左右两个位置都会变成禁区所以返回false。再比如 [0,0,0,0,0]n3可以种在位置0、2、4返回true但n4就做不到。从算法题的角度看这是一个典型的“可行性判断”问题。它不要求你输出具体种在哪也不要求求出最大数量只需要回答yes或no。这类问题通常可以用贪心、双指针或数学统计来解决而种花问题正好是贪心最容易讲明白的题目之一。1.2 题目给的隐含条件很多题解没有强调的一点是输入中已经种下的花不会违反“不能相邻”的规则。比如不会出现 [1,1,0,0] 这样的数组。这个条件意味着我们不需要去修正已有花的状态只需要在0的位置上做加法。这一点在实际写代码时非常重要因为你判断“位置i是否可以种花”时只需要看它相邻的两个位置完全不用回溯检查更远的历史。另一个隐含条件是n可能为0。当n0时不需要种任何花直接返回true。这一点看似废话却决定了一些剪枝代码能否提前返回。还有数组长度可能是1比如 [0] 时n1能种[1] 时n1不能种。如果代码里不加边界判断很容易在这类用例上翻车。另外题目通常不会限制是否允许修改输入的flowerbed数组。很多人在面试时默认原地修改其实更好的做法是先问清楚。如果面试官说“可以修改”那么原地写法最简洁如果说不可以就需要用不修改数组的版本。下面我会把两种写法都展开讲。1.3 三种典型的错误直觉我第一次做这道题时也想当然地认为只要统计空位数就行。统计0的总数后除以2结果在不少用例上是错的。比如 [0,0,0,0,0] 长度5最多能种3朵但5//2只能得到2。原因是花朵之间的间隔规则不是简单地“两个空位一朵花”边界位置可以省掉一个间隔。第二种错误是看着连续0段的长度套“除以2”的公式。比如 [0,0,1,0] 开头的两个0虽然连续但第一个0紧贴边界可以种在位置0如果机械地认为中间连续段公式(k-1)//2 0就会漏掉这一朵。更麻烦的是整个数组都是0的情况它没有“左有1”或“右有1”来界定边界很多人会把它误当成普通连续段。第三种错误也是最隐蔽的扫描时看到某个空位左右都是空位就认为可以种但没有把这个位置“变成已种植状态”导致后面相邻空位又被重复计数。比如 [0,0,0]如果只是判断而不更新数组位置1在位置0种下后本来不能种但代码会因为它左边是0就再给它一朵最后错误地算出3朵。这个问题在“不修改数组”的写法里需要通过一个变量来避免本质上都是状态管理的问题。这一节总结起来就一句话边界和状态更新是种花问题的两个最容易失分点。想明白这两点代码怎么写都不会跑偏。2. 贪心策略能种就种为什么是最优2.1 直观理解从左到右扫描花坛遇到一个空位如果它左边没有花、右边也没有花就种下一朵。这种策略叫“能种就种”它是不是太贪心会不会因为占了前面的位置而导致后面种得更少直觉上不会因为一朵花最多影响它左右两个相邻位置。如果你选择不在当前空位种而是把它留到后面那么后面你能选的位置要么不变要么更靠右而更靠右意味着占用了更靠后的空间显然不会让总数变多。用一个通俗类比你在一排空座位上选座如果某个座位两边都没人你坐下后只会影响旁边座位如果你非要不坐这里而坐到更后面旁边座位的可用性并不会变好反而可能把后排本可以坐的位置占了。所以“看到能坐就坐”在这个场景下是最优的。在种花问题里“能坐”的判断严格一些当前空位左侧为空或左边界右侧为空或右边界。满足这个条件就种不满足就跳到下一个位置。2.2 一个更严谨的替换论证如果想在面试中把贪心证明讲得滴水不漏可以用反证加替换。假设存在一个最优方案在从左到右遇到的第一个可种位置i处没有种花。那么最优方案里位置i以及i1中至少有一个位置要被后续的某些操作占用否则我们完全可以在i处种一朵然后去掉一个已有的花得到相同数量的方案。更具体地说最优方案中第一个种在i右侧的位置记为j。由于i1与i相邻如果ji1那么把j处的花移到i处不会与位置i-1冲突因为i处可种就说明i-1空移动后j处空出来也不会让任何花相邻因为原方案中j和j1之间需要隔一个空位现在j空着j1更安全。如果ji1直接把j处的花移到i处同样不会造成冲突因为i左右都空而j原来的位置空出来不会破坏任何规则。替换后的方案花数不变却与“最优方案在i处不种”矛盾。这个论证的本质是越早种植占用的后续资源越少。因此从左到右的贪心扫描一定能得到最大可种数量。面试时不需要背这段话只要理解逻辑用自己的话讲出来即可。2.3 边界上的特殊待遇线性花坛的最左边和最右边只有一个邻居。位置0只需要右边是空或右边界就能种不要求左边有什么位置m-1只需要左边是空或左边界。很多第一次写代码的人会把条件写成“flowerbed[i-1] 0 and flowerbed[i1] 0”结果在端点直接越界或者在端点处漏掉可种的机会。处理边界有两种常见姿势。第一种是在每个位置判断时加上边界条件left_ok (i 0) or (flowerbed[i-1] 0)right_ok (i m-1) or (flowerbed[i1] 0)。第二种是给数组两边各补一个0让所有真实位置都有完整的左右邻居判断逻辑就统一成“左右都为0”。我推荐初学者先写第一种因为边界条件看得见摸得着等熟悉之后再用哨兵法简化代码。2.4 时间与空间复杂度无论用上面哪种写法只需要遍历一次数组时间复杂度都是O(m)。空间复杂度取决于是否修改输入原地修改是O(1)用哨兵数组是O(m)不修改数组且只用变量记录是O(1)。在面试场景中我会主动说“原地修改只适用于允许改动输入的情况如果输入需要复用我会用变量记录最近花的版本”。这种细节虽然不影响最终正确性但能让面试官看到你具备工程意识。3. 代码实现从最简到可扩展3.1 最直接的原地修改版先看Python版本def can_place_flowers(flowerbed, n): count 0 m len(flowerbed) for i in range(m): if flowerbed[i] 0: left_ok (i 0) or (flowerbed[i - 1] 0) right_ok (i m - 1) or (flowerbed[i 1] 0) if left_ok and right_ok: flowerbed[i] 1 count 1 if count n: return True return count n这段代码的关键点有三个。第一个是left_ok和right_ok的短路顺序必须先判断边界再去访问数组否则在端点会越界。第二个是当条件满足时立刻把flowerbed[i]改成1这一步不只是在模拟种花更是为了阻止后面相邻位置重复计数。第三个是提前返回count已经达到n就不用再遍历能省下不少无谓循环。如果换成C逻辑完全一样只是需要手动管理索引类型。需要注意的是C数组没有Python那样的负索引越界访问会直接产生未定义行为所以边界判断更加重要。下面是一个可运行版本bool canPlaceFlowers(vectorint flowerbed, int n) { int count 0; int m flowerbed.size(); for (int i 0; i m; i) { if (flowerbed[i] 0) { bool leftOk (i 0) || (flowerbed[i - 1] 0); bool rightOk (i m - 1) || (flowerbed[i 1] 0); if (leftOk rightOk) { flowerbed[i] 1; if (count n) return true; } } } return count n; }C里把count和判断写在一起是常见写法但要注意count返回的是自增后的值如果这里写count判断就会出错。很多人面试时手写C容易在这种细节上翻车建议写清楚两行不要为了炫技合并。3.2 不修改原数组的写法有些场景明确要求不能修改输入数组这时可以用一个变量prev记录“左边最近一朵花的位置”。初始值设为-2表示左边很远都没有花。每遇到一个位置i如果当前是1就把prev更新为i如果当前是0并且i - prev 2说明左侧至少隔了一个空位可以尝试种花。但右侧也必须是空的所以还需要检查i1越界或flowerbed[i1]0。如果右侧为空就种下并把prev更新为i如果右侧为1则不能种也不更新prev等遍历到右侧的1时再更新。def can_place_flowers(flowerbed, n): count 0 prev -2 m len(flowerbed) for i in range(m): if flowerbed[i] 1: prev i elif i - prev 2: if i 1 m or flowerbed[i 1] 0: count 1 if count n: return True prev i return count n这个版本里prev不仅记录原始已经种下的花还记录我们新种下的花。每次种下后更新prev效果等同于把当前位置“标记为1”但没有真正改动原数组。这种写法比原地修改稍微难理解但它在保护输入数据的同时仍然保持O(1)空间是很值得掌握的技巧。3.3 加哨兵的统一写法如果觉得边界判断太啰嗦可以在原数组左右各补一个0。补出来的0不是真实地块而是“虚拟空地”它们让第一个和最后一个真实位置都有了左右邻居。这样判断就可以统一成当前是0左边是0右边是0就种。实现如下def can_place_flowers(flowerbed, n): extended [0] flowerbed [0] count 0 for i in range(1, len(extended) - 1): if extended[i] 0 and extended[i - 1] 0 and extended[i 1] 0: extended[i] 1 count 1 if count n: return True return count n哨兵法的优点是代码短、不容易漏边界缺点是新建了一个长度为m2的数组空间变成O(m)。在笔试环境里完全够用但如果面试官追问空间优化再改成前面的原地版本即可。还有一个小细节补了两个0后最后一个真实位置右边是0左边为空时就能种第一个真实位置左边是0右边为空时也能种正好满足线性边界规则。3.4 三种写法对比三种写法各有适用场景我用一张表总结写法是否修改输入空间复杂度优点缺点原地修改是O(1)最直观好调试改变了原数组不修改原数组否O(1)保护输入适合工程场景需要理解prev变量哨兵法否新建数组O(m)边界统一代码短多花一份空间我个人建议初次学习用原地修改版因为它最贴近直觉面试时如果不确定能否修改就写成“不修改原数组”的版本然后主动提一句“如果允许修改还可以更快地原地实现”笔试追求过用例时哨兵法最省心。4. 模式识别连续空段与数学解法4.1 把问题拆成连续0段除了贪心种花问题还有一个常见的数学视角。因为题目保证了已种的花不相邻所以数组可以看成若干个连续的0段段与段之间被1隔开。每一段内部能种多少花只由段长和它是否在边界决定。先说中间段。比如 [1,0,0,0,1]中间连续三个0左右都是1这个段最多能种1朵。因为三个空位中如果种在中间那个0左右都会被禁种在最左或最右也会让相邻位置被禁。再比如 [1,0,0,0,0,1]中间四个0最多也只能种1朵。可以试着种在第二个0或第三个0但无论如何只能种下一朵。当段长变成5时比如 [1,0,0,0,0,0,1]最多能种2朵。规律是中间段长度为k时最多可种 (k-1)//2 朵。边界段不一样。数组开头的连续0段因为最左边没有真正的1来限制第一个位置可以直接种。比如 [0,0,1,0,0]开头两个0后接1可以在位置0种一朵所以这个段的可种数是1。如果开头是 [0,0,0,1]可以在位置0和位置2各种一朵可种数是2。规律是开头段长度为k时最多可种 k//2 朵。末尾段同理。如果整个数组全是0没有1来分段那就相当于左右两端都是边界长度为k时可种 (k1)//2 朵。这个式子可以记忆为“边界段加一中间段减一”。但正因为有全0这种特例直接套公式容易遗漏我建议初学者还是先走贪心。4.2 公式背后的推导为什么中间段是 (k-1)//2可以想象在一段长度为k的连续空位里第一朵花必须种在段内某个位置而它会把左右各一个位置占掉。为了让数量最多我们应该隔一个空位种一朵。比如位置从0到k-1第一个可选位置是0种下后位置1不能种下一朵从位置2开始。可种位置的下标就是0,2,4...但还要保证不超过k-1且不与右边的1相邻。如果段右侧有1那么最后一个可种位置最多是k-2因为k-1紧贴右侧的1。所以可种数量是0到k-2之间偶数下标的个数也就是 (k-1)//2。边界段右侧没有1只有左侧有1所以最后一朵可以种到k-1也就是说可种位置下标取0,2,4...直到k-1数量是k//2。全0数组两侧都没有1可种位置下标也是0,2,4...直到k-1但还需要考虑首尾不相邻所以数量是(k1)//2。如果觉得这些推导太绕记住贪心代码就够了。4.3 公式与贪心怎么选做算法题时我不建议一上来就用公式原因有三个。第一公式需要先分段分段本身就要处理边界容易错第二题目问的是“能否种下n朵”用公式算出最大数量后还要比较并不比贪心快第三面试官更想听到的是“为什么能种就种是正确”的推理而不是一个记忆型公式。公式可以作为验证手段比如写完贪心后用几个例子手算对比确认代码没有明显问题。5. 环形花坛与更多变体5.1 环形花坛的额外约束有的面试官会把题目升级成“花坛首尾相连”。所谓首尾相连就是位置0和位置m-1相邻整个花坛排成一个环。这样一来原来的线性边界条件全都变了位置0不再天然可种得看位置m-1是否为空位置m-1也一样。解决环形问题的一个通用思路是拆成线性问题。由于额外冲突只发生在首尾之间可以分成两种互不重叠的情况第一种位置0不种花那么环形就退化成一条从位置1到位置m-1的线性花坛可以用标准贪心处理。第二种位置0种花那么位置1和位置m-1都被占用不能种剩下的区间[2, m-2]又是一条线性花坛。取两种情况下可种数量的最大值就是整个环形花坛的最大种植数量。如果数组长度是1环形和线性没有区别直接判断这个位置是否为空。如果长度是2两个位置互为邻居最多只能种一朵。这些特例在面试时要主动提出来免得写代码时陷入无限循环。5.2 求具体方案与在线处理原题只需要返回布尔值但面试官可能追加要求“请把种完后的数组输出”。这时只要把贪心代码里的return改成修改数组最后返回数组即可。比如原地修改版已经修改了flowerbed如果遍历结束时countn直接返回flowerbed如果countn说明无法完成任务可以返回null或者原数组。注意如果要求“必须种下n朵并输出方案”但最大可种数小于n就需要提前判断并抛出异常而不是返回一个没种满的数组。另一个扩展是数据流式到达。假设花坛的位置不是一个数组一次性给你而是每秒告诉你一个位置的状态你能在不知道未来位置的情况下做决策吗能。因为贪心只依赖“左边最近一朵有效花”和“当前位置的右邻居”你维护一个prev变量每次读入新的位置时如果当前位置为空且与prev距离足够就可以判断能否种下再继续读下一个位置。这种在线处理能力在真实系统中很有意义比如在铺满传感器的花园里某个位置的土壤湿度数据到达后系统需要立即决定要不要在附近浇水或者补种。5.3 与贪心类题目的共性种花问题非常适合用来建立贪心思维。它和另一类经典题“会议室安排”很相似每朵花占用一个位置还会占用左右各一个“缓冲区”你希望安排尽可能多的事件核心是让每次选择都尽量靠前、占用尽量少的后续资源。再比如“跳跃游戏”每步选择跳得最远的位置本质上也是局部最优能推出全局最优的例子。如果规则变得更复杂比如“每个位置周围两格内都不能有花”贪心就不一定对了因为一朵花会影响更远的范围局部最优可能堵塞后面的路。遇到这种变化通常要考虑动态规划或者搜索。所以面试时如果能主动说一句“这道题能用贪心是因为花的影响范围只有相邻两格”会显得你对问题本质有理解。6. 调试记录我踩过的三个坑6.1 越界访问我最早写Python版本时图省事直接写if flowerbed[i] 0 and flowerbed[i-1] 0 and flowerbed[i1] 0结果在 i0 时flowerbed[-1] 访问到了数组最后一个元素。Python的负索引会自动绕到尾部导致第一个位置被误判为“左侧有花”测试用例 [0,0,0] 直接返回false。这个例子很反直觉不是越界报错而是安静地给出了错误结果特别难排查。从那以后我写这种左右邻居判断一定先把边界条件放在and的最前面。在C里同样的问题会更直接越界访问是未定义行为有时崩溃有时不崩跑几组用例完全看不出问题到大数据量才暴露。所以无论用什么语言边界判断都必须显式写清楚。6.2 只计数没更新状态第二个坑出现在 [0,0,0] 上。我第一版没有把种下的位置改成1只是 count 加一然后继续遍历。当处理位置1时它左边位置0是0右边位置2是0于是又加一处理位置2也加一最终得到3而正确答案是2。问题出在位置0种花后位置1已经不能被种但我的代码不知道。这个坑让我意识到凡是“扫描过程中会根据当前决策改变后续状态”的问题必须立刻更新状态或者用一个变量记住决策。在种花问题里原地修改数组就是最直接的更新方式不修改数组时prev变量也承担了这个责任。6.3 数学公式漏了全0段有段时间我喜欢用连续0段公式因为可以快速手算。结果在 [0,0,0,0,0] 上翻车了。我的分段逻辑只考虑了“左右都有1的中间段”和“只有一边有1的边界段”全0数组没有1既不是中间段也不是边界段于是被当成普通中间段处理算出 (5-1)//2 2实际答案是3。后来我在所有公式类题的测试列表里加了一个“全零用例”专门用来拦截这种特殊情况。其实公式本身没错错的是对特殊情况的分类不完整。任何分段统计的算法都要在动手前问自己“这个数组可能完全由一种元素组成吗”养成这个习惯后不只种花问题很多边界相关的bug都能提前避免。6.4 现场自测清单每次写完代码我会用下面这组用例快速验证输入n期望输出[0]1true[1]0true[1,0,0,0,1]2false[0,0,0,0,0]3true[0,0,1,0,0]2true[1,0,0,0,0,1]2false这组用例虽然简单但覆盖了长度1、边界段、中间段、全0这四类最容易出问题的场景。如果代码能全部通过再提交错误率就会低很多。你也可以再补几个随机的大数组用例用暴力枚举去对拍不过那属于进阶操作了。写到这里种花问题的代码和原理就都讲完了。我个人做这类题最大的体会是不要因为题目短就轻视边界条件也不要因为贪心代码看起来简单就跳过证明。能写对代码只是第一步能在面试现场把“为什么能种就种一定最优”讲清楚才是真正掌握这类题目的标志。如果你还愿意多练一步可以试着把环形花坛的实现写完整或者改为输出种植方案练完之后再遇到类似的区间冲突题心里会踏实很多。
