Can Place Flowers

題目描述

給定一個整數陣列 flowerbed（0 或 1）和整數 n，判斷能否在不違反「相鄰不種花」規則下種入 n 朵花。

輸入：flowerbed = [1,0,0,0,1], n = 1
輸出：true

輸入：flowerbed = [1,0,0,0,1], n = 2
輸出：false

解題思路

遍歷花圃

用 for 迴圈從 i=0 到 flowerbed.length-1 逐一檢查每個位置

檢查條件

flowerbed[i]==0，且 i==0 或 flowerbed[i-1]==0（左邊安全），且 i==末端或 flowerbed[i+1]==0（右邊安全）

貪心種花

三個條件都滿足時，將 flowerbed[i] 設為 1（標記已種），count++

提前結束

count ≥ n 時立即回傳 true，避免多餘遍歷

程式碼

C#

csharp

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.Length; i++) {
            if (flowerbed[i] == 0) {
                bool leftEmpty = (i == 0) || (flowerbed[i - 1] == 0);
                bool rightEmpty = (i == flowerbed.Length - 1) || (flowerbed[i + 1] == 0);
                if (leftEmpty && rightEmpty) {
                    flowerbed[i] = 1; // 貪心種下
                    count++;
                    if (count >= n) return true;
                }
            }
        }
        return count >= n;
    }
}

TypeScript

typescript

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let count = 0;
    for (let i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i] === 0) {
            const leftEmpty = i === 0 || flowerbed[i - 1] === 0;
            const rightEmpty = i === flowerbed.length - 1 || flowerbed[i + 1] === 0;
            if (leftEmpty && rightEmpty) {
                flowerbed[i] = 1;
                count++;
                if (count >= n) return true;
            }
        }
    }
    return count >= n;
}

Python

python

def canPlaceFlowers(flowerbed: list[int], n: int) -> bool:
    count = 0
    for i in range(len(flowerbed)):
        if flowerbed[i] == 0:
            left_empty = (i == 0) or (flowerbed[i - 1] == 0)
            right_empty = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
            if left_empty and right_empty:
                flowerbed[i] = 1
                count += 1
                if count >= n:
                    return True
    return count >= n

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

只需一次遍歷（最多 n 步），每步做常數次判斷，因此時間 O(n)。原地修改 flowerbed 陣列不需額外空間，空間 O(1)。

邊界情況

n = 0：不需要種任何花，直接回傳 true
全為 0 的陣列：例如 [0,0,0,0,0] 可種 (length+1)/2 朵，即 3 朵（位置 0, 2, 4）
長度為 1：[0] 可種 1 朵，[1] 可種 0 朵
全為 1 的陣列：無法再種任何花，n 必須為 0 才回傳 true

圖解

[1,0,0,0,1]

掃描到 i=2→

檢查位置 2: 左=0 右=0

條件滿足→

種花 → [1,0,1,0,1]

判斷結果→

count=1 >= n=1 → true

圖表展示關鍵步驟：在 [1,0,0,0,1] 中，位置 1 的左鄰為 1 不可種，位置 2 的左右鄰居都是 0 可以種。種下後陣列變為 [1,0,1,0,1]，count 達到 n=1，提前回傳 true。

進階觀點

💡面試追問

為什麼貪心是正確的？ 假設在某個可種位置 i 不種，改在 i+2 種。那 i+2 能種的前提是 i 到 i+2 之間都是 0，但此時 i 本身也滿足條件。跳過 i 不會增加總數（最多相等），所以貪心不會錯過最優解。
能否不修改原陣列？ 可以。用一個變數 prevPlanted 記錄上一次種花的位置，檢查 i - prevPlanted > 1 取代 flowerbed[i-1] == 0 的判斷。這樣不需修改輸入。
flowerbed = [0], n = 1 會不會出錯？ 不會。i=0 時 leftEmpty 和 rightEmpty 都因邊界條件為 true，可以種花，count=1 ≥ n=1 回傳 true。

理解測驗

🤔 為什麼這題適合用貪心法？

🤔 flowerbed = [0,0,0,0,0], n = 3，結果是什麼？