LeetCode 605. 种花问题
题目描述
题意分析
花坛中的
1是已有的花，0是空位，题目保证原有花之间不相邻。不能移动原有花，要判断是否还能新增n朵，并保持相邻位置不同时有花。花坛是线性的，首尾不相邻。只要求出最多能新增多少朵，再判断是否不少于
n，不必恰好种到n才算成功。
解法：贪心扫描
核心思路
[!blue]
从左到右扫描，当前位置为空，并且左右相邻位置都没有花时，立即种下。边界外没有地块，也就不会有花，判断时把不存在的邻居视为空即可。为什么可以立刻种？固定已经处理的前缀，设
i是剩余部分最早的合法位置。若某个最优方案把下一朵新花放在更右的j，可以将它移到i：i的合法性保证不会碰到原有花或前缀中的花，而其余新花都在j右边，移动后只会离它们更远。因此不会减少总数量，可以逐次固定最左选择。每次新种的花都写回
flowerbed[i] = 1，让后面的判断同时看到原有花与刚种的花；这样下一格就会被正确排除。count只累计新种数量，扫描完即得到最大可新增数量。
解题步骤
- 初始化新增数量为零。
- 跳过已有花的位置。
- 检查左右为空或越界，满足则写入一并增加计数。
- 扫描结束后返回
count >= n。端点只检查实际存在的一侧，单个空地也可以种花。
n = 0时不需要新增，数量比较自然返回true；当前实现仍会完成扫描并修改花坛。
代码实现
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)$，当前实现修改输入数组。
关键点总结
[!green]
- 只统计新种花数，原有花不计入需求。
- 最早合法选择可以通过交换论证保留最优数量。
- 越界不是已有花，边缘位置仍能种植。
易错点总结
[!yellow]
- 只计数不写回：后续位置看不到刚种下的花，可能错误地连续种植。
- 用 count==n 判断：最多能种更多也应返回 true。
- 不检查当前位置是否已有花：重复计入原有花。
- 短路边界判断放在数组读取后：首尾位置会越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 198. 打家劫舍 | 中等 | 同样存在相邻位置不能同时选择的限制，本题已有花位形成固定约束，目标是再放尽可能多的花。 |
| 213. 打家劫舍 II | 中等 | 原题首尾也相邻，本题花坛是线性的，端点只有一个邻居。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！