本文详解 leetcode 605 题“种花问题”的高效解法，指出原始尝试中冗余数组和边界处理错误的问题，提供单次遍历、原地判断的优化方案，并附带可运行代码与关键边界说明。
本文详解 leetcode 605 题“种花问题”的高效解法，指出原始尝试中冗余数组和边界处理错误的问题，提供单次遍历、原地判断的优化方案，并附带可运行代码与关键边界说明。
原始实现试图通过预收集所有空位索引（empty[] 数组）再逐个尝试栽种，存在三方面根本性缺陷：
- 逻辑错误：对边界索引（如 i=0 或 i=flowerbed.length-1）的邻位检查未做安全偏移，导致 flowerbed[-1] 或 flowerbed[length] 越界访问（虽 Java 中未显式报错，但 v/x 计算后取值为 0，造成误判）；
- 状态不同步：修改 flowerbed[empty[h]] = 1 后，后续循环仍可能重复检查已被占用的位置，且 empty[] 数组未动态更新，导致同一空位被多次尝试；
- 时间与空间低效：额外分配 O(n) 空间存储空位，嵌套循环使最坏时间复杂度达 O(n²)，违背线性解题初衷。
✅ 正确思路是一次遍历 + 贪心放置：
- 对每个位置 i，检查其自身及左右邻居是否均为 0；
- 左邻居用 i == 0 || flowerbed[i-1] == 0 安全判断（避免越界）；
- 右邻居用 i == flowerbed.length-1 || flowerbed[i+1] == 0 安全判断；
- 满足条件则栽种（flowerbed[i] = 1），并计数 count++；
- 一旦 count >= n，立即返回 true。
以下是优化后的标准解法：
public class Solution {
public static boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0) return true; // 边界：无需栽种，直接成功
int count = 0;
for (int i = 0; i < flowerbed.length; i++) {
// 检查当前位置是否为空，且左右邻居（若存在）也为空
boolean canPlant = flowerbed[i] == 0
&& (i == 0 || flowerbed[i - 1] == 0)
&& (i == flowerbed.length - 1 || flowerbed[i + 1] == 0);
if (canPlant) {
flowerbed[i] = 1; // 栽种
count++;
if (count >= n) return true; // 提前终止
}
}
return count >= n;
}
}? 关键注意事项：
- 边界处理必须显式：首尾位置只有一侧邻居，不可简单用 flowerbed[i-1] 和 flowerbed[i+1] 直接访问；
- 贪心有效性：从左到右尽可能早栽种，不会影响后续最优解——因为延迟栽种只会减少右侧可用空间，而提前栽种不会产生负向影响；
- 原地修改安全：栽种后立即更新 flowerbed[i]，确保后续位置判断基于最新状态；
- 提前返回提升性能：无需遍历完全部数组，满足 n 即刻返回，平均时间复杂度接近 O(n)，最坏 O(n)。
该解法空间复杂度 O(1)，时间复杂度 O(n)，逻辑清晰、鲁棒性强，是此题的标准工业级实现。
