LeetCode 605. 种花问题
目录
题目描述
题意分析
一条花坛用数组
flowerbed表示，0是空地、1是已经种了花。规则是任意两朵花不能相邻（原有的花已经满足这个规则）。给定还要新种n朵，问能不能种下。「不能相邻」这条约束是局部的：某个位置能不能种，只取决于它自己和它左右各一格，跟更远的位置毫无关系。这一点非常关键——它意味着不需要任何全局信息，一趟从左到右的扫描就足以做出所有决策。
注意返回值是布尔而不是「最多能种几朵」。这给了一个小优化空间（种够
n朵就可以提前返回真），但也带来一个陷阱：n可能是0，此时不种任何花就已经满足，必须返回真。边界情形值得单独想清楚：数组的第一个位置没有左邻居、最后一个位置没有右邻居。正确的处理是把越界的一侧视作空地——花坛之外不会有花，所以那一侧的约束天然满足。若把越界当成「有花」，
[0]这种单格花坛就会被判成种不了，而正确答案是能种一朵。约束方面，数组长度是线性规模，
n也不超过数组长度量级，显然目标是 $O(m)$ 一趟扫描、$O(1)$ 额外空间。题目没有任何暗示需要动态规划——事实上「相邻不能同时选、求最多能选几个」确实是打家劫舍式的 DP 模型，但因为这里每个位置的收益都是 1（而不是各不相同的权值），最优解可以用贪心直接构造出来，不必上 DP。还有一处容易忽略的隐含前提：题目保证输入的
flowerbed本身是合法的（不存在两朵相邻的花）。所以扫描时只需保证新种的花不破坏规则，不需要校验原有布局。
解法：贪心扫描
核心思路
先看这个问题的本质：把花坛里连续的空地段挑出来，在每段里尽量多种花，且不能与段两端已有的花相邻。这本质上是「相邻不可同选、求最大独立集」的一维版本，用打家劫舍那套 DP（
dp[i] = max(dp[i-1], dp[i-2] + 1)）当然能做，$O(m)$ 时间、$O(1)$ 空间。但对本题来说这是多余的：每个位置的收益都是 1，完全同质，不存在「牺牲眼前换取更大收益」的可能，所以最优解可以贪心地一步步构造出来。贪心策略是：从左往右扫，遇到能种的位置立刻种下。
为什么这样不会更差？关键在于「种在越靠左的位置，对右边的封锁越少」。假设某个最优方案在位置
j种了一朵花，而贪心在更靠左的i（i < j）种下了一朵。由于扫描到i时判定为可种，说明i-1、i、i+1三格都空；把最优方案里j那朵挪到i，只可能解除j附近的封锁、不会新增任何冲突（i处本来就合法），因此改造后的方案花数不变且仍然合法。反复施行这个交换，任何最优方案都能被改造成贪心产出的方案，所以贪心结果就是最优。具体到实现，判定条件是三个格子同时为空：当前位置
flowerbed[i] == 0、左邻居空或不存在、右邻居空或不存在。「不存在即视为空」用短路表达式i == 0 || flowerbed[i-1] == 0一行写完，既避免了越界访问，也省掉了为首尾各写一段特判。种下之后必须真的把
flowerbed[i]改成1。这一步不是可选的记账，而是让后续判断正确的必要动作：下一个位置i+1会检查它的左邻居，如果不写回，它会以为左边仍是空地从而种下第二朵，直接违反规则。换句话说，数组本身充当了「已做决策」的状态载体，这是原地贪心的常见手法。循环不变量：扫描到位置
i时，flowerbed[0..i]这一前缀已经是合法布局，且count等于其中新种的花数；同时这个前缀上的新种花数已达到该前缀所能容纳的最大值。扫完全程后count就是全花坛最多能新种的朵数，与n比较即得答案。
解题步骤
- 准备计数器
count = 0，取出数组长度len。为什么：count统计的是新种的花数，不含原有的花，所以从0起算；长度提到循环外取，避免在越界判断里反复求值。- 从左到右遍历每个位置
i。为什么：贪心要求「尽早种下」，方向必须是从左往右；顺序一旦反过来（从右往左）结论依然成立（对称），但绝不能左右横跳，否则「已决策前缀」这个不变量就不成立了。flowerbed[i] != 0时直接跳过。为什么：该位置已经有花，既不能再种、也不需要处理；提前continue让后面的判断只需要关心空地这一种情形。- 判断左侧：
i == 0 || flowerbed[i - 1] == 0。为什么：i == 0时左边是花坛外部，不可能有花，视作空地；短路求值保证了i == 0时不会去访问flowerbed[-1]，两个目的一行达成。- 判断右侧：
i == len - 1 || flowerbed[i + 1] == 0。为什么：同理，末尾位置的右边是花坛外部，视作空地；短路顺序不能反，写成flowerbed[i + 1] == 0 || i == len - 1会先越界再判断。- 两侧都空时，把
flowerbed[i]置为1并让count++。为什么：置1是必须的——下一轮i + 1会读取它作为左邻居，不写回就会连着种两朵；count++记录新增的花数。两个动作必须成对出现。- 循环结束后返回
count >= n。为什么：count是最多能新种的朵数，只要不少于需求就返回真；用>=而不是==，因为种得比需要的多同样满足条件。n == 0时这个式子恒为真，边界自然覆盖。以
flowerbed = [1, 0, 0, 0, 1], n = 1走一遍（正确答案是true）。初始count = 0，len = 5。
i = 0：flowerbed[0] == 1，跳过。
i = 1：值为0。左侧i != 0，检查flowerbed[0] == 1，非空——leftEmpty为假，不种。
i = 2：值为0。左侧flowerbed[1] == 0为空；右侧flowerbed[3] == 0为空。两侧都空，种下！flowerbed变成[1, 0, 1, 0, 1]，count = 1。
i = 3：值为0。左侧flowerbed[2]此刻已经是1——正是刚才写回的那朵——leftEmpty为假，不种。如果上一步只加计数而不写回数组，这里会误判为可种，得到count = 2并且布局里出现相邻的两朵花。
i = 4：值为1，跳过。返回
1 >= 1即true。再看同一个花坛但
n = 2：count仍然是1，返回1 >= 2即false，符合预期。最后看边界例子
flowerbed = [0], n = 1：i = 0时值为0，左侧因i == 0直接判为空，右侧因i == len - 1直接判为空，于是种下，count = 1，返回true。若把越界一侧当成「有花」，这里会返回false——这就是「越界视作空地」这条规则的价值。
代码实现
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
// count 只统计新种的花，不含原有的花。
int count = 0;
int len = flowerbed.length;
for (int i = 0; i < len; i++) {
if (flowerbed[i] != 0) {
continue;
}
// 短路求值：越界一侧视作空地，同时避免访问越界下标。
boolean leftEmpty = i == 0 || flowerbed[i - 1] == 0;
boolean rightEmpty = i == len - 1 || flowerbed[i + 1] == 0;
if (leftEmpty && rightEmpty) {
// 必须写回数组：下一轮要靠它判断左邻居，否则会连种两朵。
flowerbed[i] = 1;
count++;
}
}
return count >= n;
}
}
func canPlaceFlowers(flowerbed []int, n int) bool {
// count 只统计新种的花，不含原有的花。
count := 0
length := len(flowerbed)
for i := 0; i < length; i++ {
if flowerbed[i] != 0 {
continue
}
// 短路求值：越界一侧视作空地，同时避免访问越界下标。
leftEmpty := i == 0 || flowerbed[i-1] == 0
rightEmpty := i == length-1 || flowerbed[i+1] == 0
if leftEmpty && rightEmpty {
// 必须写回数组：下一轮要靠它判断左邻居，否则会连种两朵。
flowerbed[i] = 1
count++
}
}
return count >= n
}
复杂度分析
- 时间复杂度：$O(m)$，
m为花坛长度。凭什么：只有一层从左到右的循环，每个位置做常数次比较与至多两次赋值；没有回退、没有嵌套循环，每个格子恰好被作为「当前位置」访问一次、被作为「邻居」读取至多两次。- 空间复杂度：$O(1)$。凭什么：只用了
count、len、i和两个布尔临时量，全是标量；花的种植状态直接写回入参数组，没有额外分配。代价是修改了入参——若调用方不允许原地修改，可以改用一个变量记住「上一个位置是否被新种」来替代写回，空间仍是 $O(1)$。
关键点总结
- 约束是局部的（只看左右各一格）时，就可以一趟线性扫描解决，不需要任何全局结构。判断一道题该用扫描还是 DP，先问「当前决策依赖多远的信息」。
- 「相邻不可同选、求最多选几个」本是打家劫舍式 DP，但当每个位置的收益完全相同时，贪心即最优。收益一旦各不相同（比如每个位置能种的花数不一样），贪心立刻失效、必须回到 DP——能说出这条分界线，比会写代码更重要。
- 贪心的正确性要用交换论证说明：把最优解里靠右的选择往左挪到贪心的位置，方案数不变且仍合法，因此贪心不劣于任何最优解。面试中被追问「凭什么能贪」，这就是标准答法。
- 原地修改数组来记录已做决策，是一维贪心的常用手法。写回这一步不是记账而是逻辑必需——后续判断要读它。凡是「决策会影响后续判定」的扫描，都要检查状态有没有真正落地。
- 越界侧视作空地，用
i == 0 || ...的短路表达式一行搞定，既是语义正确（花坛外不会有花），也避免了越界访问。短路的顺序不能颠倒。- 面试延伸：被追问「不许修改入参怎么办」时，答案是用一个布尔变量记住上一格是否刚被种下，或者按「连续空地段长度
L能种 $\lfloor (L+1)/2 \rfloor$ 朵」的公式分段计算；被追问「能否提前退出」时，可以在count >= n时立刻返回真，最坏复杂度不变但平均更快。
易错点总结
- 种花时只
count++而不把flowerbed[i]置为1：flowerbed = [0, 0], n = 2→i = 0种下后没有写回，i = 1仍以为左邻是空地也种下，count = 2返回true；但这两朵花相邻并不合法，实际最多只能种 1 朵，正确答案是false。- 把越界一侧当成「有花」：
flowerbed = [0], n = 1→ 左右都被判为不可用，返回false，正确答案是true。- 短路顺序写反成
flowerbed[i - 1] == 0 || i == 0：i = 0→ 先访问flowerbed[-1]，直接数组越界抛异常。- 右邻界判断写成
i == len而不是i == len - 1：i走到最后一格 → 条件不成立，转而访问flowerbed[len]，越界崩溃。- 忘记先判断
flowerbed[i] != 0：flowerbed = [1, 0, 1]→ 在i = 0处发现左侧越界为空、右侧flowerbed[1] == 0也为空，于是在已有花的位置又"种"一朵，count虚增。- 返回
count == n而不是count >= n：flowerbed = [0, 0, 0, 0, 0], n = 1→ 最多能种 3 朵，3 == 1为假，返回false，而正确答案是true。- 没有处理
n == 0：若代码里写了if (flowerbed.length == 0) return false之类的前置分支 →n = 0时本该返回true（不种也满足），却返回false。- 用
dp[i] = max(dp[i-1], dp[i-2] + 1)却忽略原有的花：flowerbed = [1, 0, 0, 0, 1]→ DP 若不把已有花位置强制为「不可选且封锁邻居」，会算出能种 2 朵，正确答案是 1 朵。- 试图用「连续空地段长度
L能种L / 2朵」的公式：段长为3的中间空地（两端有花）→ 公式给出1，正确；但对首尾开放的段（如整个数组全空、长度 3）→ 公式给出1，而实际能种2朵。正确公式要区分段两端是否邻花，直接扫描反而不易错。- 在循环中提前
return true却把判断写在种花之前：count尚未包含本轮 →n恰好等于最终朵数时会漏判一轮，返回false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 198. 打家劫舍 | 中等 | 同为「相邻不可同选」，但每间房收益不同，贪心失效必须用 DP |
| 213. 打家劫舍 II | 中等 | 在 198 基础上首尾相连成环，需拆成两条线性链分别求解再取最大 |
| 55. 跳跃游戏 | 中等 | 同为一趟贪心扫描，但维护的是「能到达的最远下标」而非逐格判定 |
| 45. 跳跃游戏 II | 中等 | 求最少步数，贪心要按「当前层能覆盖的右边界」分层推进 |
| 452. 用最少数量的箭引爆气球 | 中等 | 同样用交换论证证明贪心，但需先按右端点排序才能保证「尽早射」最优 |
| 435. 无重叠区间 | 中等 | 与 452 互为补集，考的是「保留最多不重叠区间」的等价转换 |
| 763. 划分字母区间 | 中等 | 需先预处理每个字母的最后出现位置，再用贪心扫描切分，依赖全局信息 |
| 134. 加油站 | 中等 | 贪心结论更隐蔽：总量为正必有解，且失败点之后的位置才可能是起点 |