605. 种花问题

题目描述

花坛里 1=已种、0=空，相邻不能都种花。问能否再种下 n 朵。

思路解析

从左扫到右：当前格是 0、且左边（或越界）是 0、右边（或越界）也是 0，就种下去（置 1）、计数 +1。能种就种是最优——不会挡住更多机会。

i=0 · 已种：下标 0 已种花（1），跳过。

i=1 · 左边有花：下标 1 是空的，但左边 0 号位有花，不能种。

i=2 · 两边都空 · 种！：下标 2 自己空、左右（1 和 3）也空，种下一朵！把它置 1，count=1。已满足 n=1。

i=3 · 左边刚种：下标 3 空，但左边 2 刚种了花，不能种。注意要看更新后的花坛。

结论：一共能种下 1 朵 ≥ 需要的 1 朵，返回 true。

「能种就种」为啥最优？早种不会减少后面的机会。这类「局部最优 = 全局最优」的判断，是贪心的核心直觉。

参考代码（Python）

1count = 0
2for i in range(len(bed)):
3    left  = (i == 0) or bed[i-1] == 0
4    right = (i == len(bed)-1) or bed[i+1] == 0
5    if bed[i] == 0 and left and right:
6        bed[i] = 1; count += 1        # 种下，影响后面
7return count >= n

复杂度分析

• 时间复杂度：O(n) —— 扫一遍
• 空间复杂度：O(1) —— 原地，几个变量

套路模板

记住骨架：从左到右、局部满足就取、取后更新影响后续。分发饼干、无重叠区间都是这类扫描贪心。

1count = 0
2for i in range(n):
3    if 当前可取(i):                  # 局部判断
4        取它(); count += 1          # 取了要更新状态
5return count 满足要求?

易错点

• ❌ 判断时不更新 bed → ✅ 种下后置 bed[i]=1（不更新会让相邻格也被误判为可种）
• ❌ 边界没当作"空" → ✅ i==0 或 i==n-1 时缺的邻居算空（首尾只有一个邻居）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。