本文详解 leetcode 605 题“种花问题”的高效贪心解法，指出原始尝试中使用额外空位数组和嵌套循环的缺陷，提供单次遍历、原地判断的简洁实现，并覆盖首尾边界、连续零、零长度等关键边界条件。
本文详解 leetcode 605 题“种花问题”的高效贪心解法，指出原始尝试中使用额外空位数组和嵌套循环的缺陷，提供单次遍历、原地判断的简洁实现，并覆盖首尾边界、连续零、零长度等关键边界条件。
原始代码试图通过预收集所有空位索引（empty[]），再对每个空位反复检查是否可种花，存在三处根本性问题：
- 逻辑错误：v = empty[h] - 1 >= 0 ? empty[h] - 1 : 0 在 empty[h] == 0 时将 v 设为 0，导致误判左邻位（实际应为越界视为安全，而非取 flowerbed[0]）；
- 状态不同步：修改 flowerbed[empty[h]] = 1 后未更新 empty[]，后续循环仍会重复检查已占用位置；
- 时间复杂度失控：外层 for (j=1; j<=n; j++) 与内层遍历 empty[] 形成 O(n×m) 嵌套，远超线性要求。
正确的解法应采用贪心策略 + 单次线性扫描：从左到右遍历，对每个位置 i 判断是否满足 flowerbed[i] == 0 且左右邻居（存在时）均为 0，即可立即种花并计数。关键在于统一处理边界——将越界位置视为 0（即安全）。
以下是优化后的标准实现：
public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0) return true;
int count = 0;
for (int i = 0; i < flowerbed.length; i++) {
// 检查当前位置是否为空，且左右邻居（越界视为0）均为空
int left = (i == 0) ? 0 : flowerbed[i - 1];
int right = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1];
if (flowerbed[i] == 0 && left == 0 && right == 0) {
flowerbed[i] = 1; // 种花
count++;
if (count >= n) return true;
}
}
return count >= n;
}
}核心要点说明：
- ✅ 边界安全处理：i == 0 时 left 视为 0；i == len-1 时 right 视为 0，避免数组越界且逻辑符合题意（首尾无左/右邻，天然满足“不相邻”）；
- ✅ 即时终止：一旦 count >= n 立即返回 true，无需遍历剩余部分；
- ✅ 空间最优：仅用常量额外空间，原地修改（若题目禁止修改输入，可加注释说明或复制数组）；
- ⚠️ 注意陷阱：连续多个 0（如 [0,0,0,0]）时，贪心策略会优先在最左可能位置种花（i=0 → i=2），这恰好最大化可种植数，证明贪心正确性。
该解法时间复杂度 O(n)，空间复杂度 O(1)，稳健覆盖所有边界场景（空数组、单元素、全零、全一、n=0 等），是面试与工程实践中推荐的标准解法。
