📘 題目敘述
給定一個整數陣列 flowerbed，其中：
0表示空地1表示已經種花
規則是：不能在相鄰的位置種花。
請判斷是否能在不違反規則的情況下，再種下 n 朵花。
條件限制
1 ≤ flowerbed.length ≤ 2 * 10^4flowerbed[i]只會是0或10 ≤ n ≤ flowerbed.length
🧠 解題思路
這題我沒有選擇「一格一格嘗試能不能種花」的模擬方式，而是換一個角度，把整個花圃看成由多段連續的空地（0）所組成。
問題就可以轉換成：
每一段連續的 0，在不和相鄰花衝突的情況下，最多可以放幾朵花？
只要把所有區段「最多能放的花數」加起來，再和 n 比較，就能知道答案。
所有變數
block：代表「目前正在累積的連續空地長度」。all：代表「在理想情況下，目前最多總共可以放幾朵花」。
我會從左到右掃描整個 flowerbed，一邊累積 block，一邊在適當時機把它結算進 all。
為什麼 block 一開始設為 1？
這是一個用來統一處理邊界的小技巧。
在花圃最左邊：
- 如果一開始是
0，左邊實際上是沒有花的 - 等同於「左邊有一個不能放花的邊界」
把 block 初始化為 1，就可以讓「左邊界的空地段」和「中間被花夾住的空地段」用同一套公式處理，不需要額外寫特例。
🪜 主要流程步驟
情況一：遇到 0（空地）
- 代表目前這一段空地還在延續
- 我只做一件事：讓
block加一 - 不急著計算能放幾朵花，等這段空地結束再一起算
情況二：遇到 1（已種花）
- 代表前面那一整段連續的
0已經結束 - 這時可以「結算」這一段空地最多能放幾朵花
對於被花（或左邊界）夾住的空地區段，最多能放的花數是：
(block - 1) / 2
原因是：
- 相鄰不能種花
- 每放一朵花，左右都至少要空一格
(block - 1)正好把邊界影響扣掉
結算完後，把 block 重設，準備累積下一段空地。
情況三：走到花圃最後一格
- 如果最後是
0，代表有一段空地尚未被結算 - 尾端沒有右邊界的花，因此計算方式略有不同
尾端空地最多能放的花數為：
block / 2
把這個結果加進 all，就完成所有區段的統計。
最後判斷邏輯
all代表在「最理想情況下」最多能放的花數- 如果
all >= n：代表一定存在一種合法的種花方式 - 否則：不論怎麼安排，都不可能放下
n朵花
整體邏輯總結
這題的關鍵不在模擬，而在轉換問題的角度：
- 把「能不能種花」轉成「連續空地的最大容納量」
- 每一段空地都可以獨立計算
- 用一次線性掃描就能完成所有計算
這樣的寫法：
- 時間複雜度是
O(n) - 不需要反覆嘗試或回溯
- 邏輯清楚，也容易驗證正確性
💻 程式碼實作
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int m = flowerbed.size();
int block = 1, all = 0;
for (int i = 0; i < m; i++) {
if ((flowerbed[i] == 1 && block > 0)) {
all += (block - 1) / 2;
block = 0;
} else if (flowerbed[i] == 0) {
block += 1;
}
if (i == (m - 1)) {
all += block / 2;
}
}
if (all >= n) {
return true;
}
return false;
}
};
🔗 題目連結
https://leetcode.com/problems/can-place-flowers/