一、前言

本题为LeetCode第605题，是一道 贪心算法 相关的算法题，难度简单。

本题链接：#605. 种花问题

二、题目

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

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

示例1：

Input:  flowerbed = [1,0,0,0,1], n = 1
Output: true

示例2：

Input:  flowerbed = [1,0,0,0,1], n = 2
Output: false

三、思路

        实质上该题也是一道求最优解的算法题。只需求解可种花数的最大值，再和 n 做比较，大于等于 n 返回 true ，小于 n 返回 false。由于同时分析所有地块比较复杂，我们可以从左往右对所有地块进行逐一分析，因此可以使用贪心算法。（注意：初始数组也无法违背种植规则）

1. 从左往右分析每一地块，若该地块有花（为1），则忽略该地块和下一个地块，分析下下个地块；
2. 若该地块无花（为0），则判断下一个地块是否有花；
3. 若下一个地块无花（为0），则该地块可以种花，分析下下个地块；
4. 若下一个地块有花（为1），则跳转至步骤1；
5. 循环往复，直至最后一个地块（由于最后一个地块右边没有地块，所以假设最后一个地块右边是一个无花（为0）的地块）。

四、Java代码

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        // 假设最后一个地块右边是一个无花（为0）的地块
        int size = flowerbed.length;
        flowerbed = Arrays.copyOf(flowerbed, size + 1);
        flowerbed[size] = 0;

        int count = 0;
        for(int i = 0; i < size; i++) {
            if( flowerbed[i] == 1 ) {
                i++;
                continue;
            }else {
                if( flowerbed[i+1] == 0 ) {
                    count++;
                    i++;
                }
            }
        }

        return count - n >= 0;
    }
}