LeetCode：605. 种花问题

方法一：贪心

判断能否在不打破种植规则的情况下在花坛内种入 nn 朵花，从贪心的角度考虑，应该在不打破种植规则的情况下种入尽可能多的花，然后判断可以种入的花的最多数量是否大于或等于 nn。 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

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

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

提示：

1 <= flowerbed.length <= 2 * 104 flowerbed[i] 为 0 或 1 flowerbed 中不存在相邻的两朵花 0 <= n <= flowerbed.length

来源：力扣（LeetCode） 链接：leetcode.cn/problems/ca…

思路

假设花坛的下标 ii 和下标 jj 处都种植了花，其中 j-i \ge 2j−i≥2，且在下标 [i+1,j-1][i+1,j−1] 范围内没有种植花，则只有当 j-i \ge 4j−i≥4 时才可以在下标 ii 和下标 jj 之间种植更多的花，且可以种植花的下标范围是 [i+2,j-2][i+2,j−2]。可以种植花的位置数是 p=j-i-3p=j−i−3，当 pp 是奇数时最多可以在该范围内种植 (p+1)/2(p+1)/2 朵花，当 pp 是偶数时最多可以在该范围内种植 p/2p/2 朵花。由于当 pp 是偶数时，在整数除法的规则下 p/2p/2 和 (p+1)/2(p+1)/2 相等，因此无论 pp 是奇数还是偶数，都是最多可以在该范围内种植 (p+1)/2(p+1)/2 朵花，即最多可以在该范围内种植 (j-i-2)/2(j−i−2)/2 朵花。

上述情况是在已有的两朵花之间种植花的情况（已有的两朵花之间没有别的花）。假设花坛的下标 ll 处是最左边的已经种植的花，下标 rr 处是最右边的已经种植的花（即对于任意 k<lk<l 或 k>rk>r 都有 \textit{flowerbed}[k]=0flowerbed[k]=0），如何计算在下标 ll 左边最多可以种植多少朵花以及在下标 rr 右边最多可以种植多少朵花？

下标 ll 左边有 ll 个位置，当 l<2l<2 时无法在下标 ll 左边种植花，当 l \ge 2l≥2 时可以在下标范围 [0,l-2][0,l−2] 范围内种植花，可以种植花的位置数是 l-1l−1，最多可以种植 l/2l/2 朵花。

令 mm 为数组 \textit{flowerbed}flowerbed 的长度，下标 rr 右边有 m-r-1m−r−1 个位置，可以种植花的位置数是 m-r-2m−r−2，最多可以种植 (m-r-1)/2(m−r−1)/2 朵花。

如果花坛上没有任何花朵，则有 mm 个位置可以种植花，最多可以种植 (m+1)/2(m+1)/2 朵花。

根据上述计算方法，计算花坛中可以种入的花的最多数量，判断是否大于或等于 nn 即可。具体做法如下。

维护 \textit{prev}prev 表示上一朵已经种植的花的下标位置，初始时 \textit{prev}=-1prev=−1，表示尚未遇到任何已经种植的花。

从左往右遍历数组 \textit{flowerbed}flowerbed，当遇到 \textit{flowerbed}[i]=1flowerbed[i]=1 时根据 \textit{prev}prev 和 ii 的值计算上一个区间内可以种植花的最多数量，然后令 \textit{prev}=iprev=i，继续遍历数组 \textit{flowerbed}flowerbed 剩下的元素。

遍历数组 \textit{flowerbed}flowerbed 结束后，根据数组 \textit{prev}prev 和长度 mm 的值计算最后一个区间内可以种植花的最多数量。

判断整个花坛内可以种入的花的最多数量是否大于或等于 nn。

由于只需要判断能否在不打破种植规则的情况下在花坛内种入 nn 朵花，不需要具体知道最多可以在花坛内种入多少朵花，因此可以在循环内进行优化，当可以种入的花的数量已经达到 nn，则可以直接返回 \text{true}true，不需要继续计算数组剩下的部分。

作者：LeetCode-Solution

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