605. 种花问题

题目描述

一排花坛用数组 flowerbed 表示，flowerbed[i] = 1 表示第 i 块地已经种了花，0 表示空着。规则是任意两朵花不能种在相邻的两块地上。

再给一个整数 n。判断能否在空地上再种下 n 朵新花，并且种完后仍然没有两朵花相邻。

可以做到返回 true，否则返回 false。

示例 1

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

解释：中间的下标 2 两侧都是空地，可以种 1 朵。

示例 2

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

解释：只有下标 2 能种，无法种下 2 朵。

数据范围

1 <= flowerbed.length <= 2 * 10^4
flowerbed[i] 为 0 或 1。
初始的 flowerbed 中没有相邻的两朵花。
0 <= n <= flowerbed.length

解题思路：补边贪心种花

在两端各补一个 0，这样边界上的地块不用特判。从左到右扫描：如果当前地块和左右两个邻居都是 0，就立刻种下（置 1）并让 n 减 1。能种就尽早种：种在更靠左的位置，对右边的影响最小，不会让总数变少。最后判断 n ≤ 0。

为什么正确

扫描到 i 时，左边已经种下的花数是前缀里能种的最大值，且种下的花都已写回 bed，后面判断左邻居时能看到。

复杂度分析

时间 O(m)，空间 O(m)（补边后的副本；也可原地 O(1)）。

易错点

种下后一定要把 bed[i] 置 1，否则下一个位置会误以为左邻是空地，连续种两朵。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        bed = [0] + flowerbed + [0]
        for i in range(1, len(bed) - 1):
            if bed[i - 1] == 0 and bed[i] == 0 and bed[i + 1] == 0:
                bed[i] = 1
                n -= 1
        return n <= 0

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int[] bed = new int[flowerbed.length + 2]; System.arraycopy(flowerbed, 0, bed, 1, flowerbed.length);
        for (int i = 1; i < bed.length - 1; i++) {
            if (bed[i - 1] == 0 && bed[i] == 0 && bed[i + 1] == 0) {
                bed[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
}

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        vector<int> bed(flowerbed.size() + 2, 0); copy(flowerbed.begin(), flowerbed.end(), bed.begin() + 1);
        for (int i = 1; i < (int)bed.size() - 1; i++) {
            if (bed[i - 1] == 0 && bed[i] == 0 && bed[i + 1] == 0) {
                bed[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
};

func canPlaceFlowers(flowerbed []int, n int) bool {
	bed := append(append([]int{0}, flowerbed...), 0)
	for i := 1; i < len(bed)-1; i++ {
		if bed[i-1] == 0 && bed[i] == 0 && bed[i+1] == 0 {
			bed[i] = 1
			n--
		}
	}
	return n <= 0
}

var canPlaceFlowers = function(flowerbed, n) {
    const bed = [0, ...flowerbed, 0];
    for (let i = 1; i < bed.length - 1; i++) {
        if (bed[i - 1] === 0 && bed[i] === 0 && bed[i + 1] === 0) {
            bed[i] = 1;
            n--;
        }
    }
    return n <= 0;
};

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

载入编辑器，自己跑一遍 →

其他解法

补边贪心逐格尝试种花，直观但要复制数组；按空位段计数用公式一次算出每段的容量，只用常数空间。

解法 2：按空位段计数时间 O(m)，空间 O(1)

不修改花坛，只统计相邻两朵已种花之间的空位。两朵花在下标 i 和 j 时，中间最多还能种 (j − i − 2) / 2 朵。开头和结尾只有一侧有花，可以想象在下标 −2 和 m + 1 各有一朵花，套用同一公式。求和后与 n 比较。

不复制、不修改输入，只用常数空间。代价是要推导空位段公式并处理两端，容易在边界上出错。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        m = len(flowerbed)
        count = 0
        prev = -2
        for i in range(m):
            if flowerbed[i] == 1:
                count += (i - prev - 2) // 2
                prev = i
        count += (m + 1 - prev - 2) // 2
        return count >= n

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int m = flowerbed.length, count = 0, prev = -2;
        for (int i = 0; i < m; i++) {
            if (flowerbed[i] == 1) {
                count += (i - prev - 2) / 2;
                prev = i;
            }
        }
        count += (m + 1 - prev - 2) / 2;
        return count >= n;
    }
}

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int m = flowerbed.size(), count = 0, prev = -2;
        for (int i = 0; i < m; i++) {
            if (flowerbed[i] == 1) {
                count += (i - prev - 2) / 2;
                prev = i;
            }
        }
        count += (m + 1 - prev - 2) / 2;
        return count >= n;
    }
};

func canPlaceFlowers(flowerbed []int, n int) bool {
	m, count, prev := len(flowerbed), 0, -2
	for i := 0; i < m; i++ {
		if flowerbed[i] == 1 {
			count += (i - prev - 2) / 2
			prev = i
		}
	}
	count += (m + 1 - prev - 2) / 2
	return count >= n
}

var canPlaceFlowers = function(flowerbed, n) {
    const m = flowerbed.length;
    let count = 0, prev = -2;
    for (let i = 0; i < m; i++) {
        if (flowerbed[i] === 1) {
            count += Math.floor((i - prev - 2) / 2);
            prev = i;
        }
    }
    count += Math.floor((m + 1 - prev - 2) / 2);
    return count >= n;
};

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    const m = flowerbed.length;
    let count = 0, prev = -2;
    for (let i = 0; i < m; i++) {
        if (flowerbed[i] === 1) {
            count += Math.floor((i - prev - 2) / 2);
            prev = i;
        }
    }
    count += Math.floor((m + 1 - prev - 2) / 2);
    return count >= n;
}

贪心专题的其他题目

查看贪心全部题目 →