LC605. 种花问题

题目描述

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。 给你一个整数数组 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

题目解析

好的，没问题。我是你的算法老师，AlgoMooc。我们一起来把这道“种花问题”彻底搞懂，保证零基础也能听明白。

---

题目在说什么

这道题其实就是一个种花的小游戏，但有个严格的规则：花不能种在相邻的地块上。

想象一下，你有一个花坛，它被分成了很多小格子。每个格子要么已经种了花（用数字 1 表示），要么是空的（用数字 0 表示）。现在，你手里有 n 朵新花要种进去。

规则是：任何两朵花都不能挨着。也就是说，如果你在某个空位种了花，它左边和右边的格子就都不能再种了，否则它们会打架死掉。

题目给你一个花坛的现状（一个由 0 和 1 组成的数组）和一个数字 n，问你：能不能在不违反规则的情况下，把这 `n` 朵新花都种进去？ 能就返回 true，不能就返回 false。

举个栗子： 花坛是 [1,0,0,0,1]，这表示第一个和最后一个格子已经种了花。

• 如果 n = 1，我们可以种在第三个格子（下标2），这样它左边是空，右边也是空，没问题。所以答案是 true。
• 如果 n = 2，我们最多只能种一朵（比如种在第三个格子），因为种完一朵后，它的左右邻居都不能种了。所以答案是 false。

---

思路是怎么来的

这个问题，新手最容易犯的错误就是“每个空位都去试试看能不能种”，这样会很慢，而且容易把自己绕晕。

我们换个思路，用贪心的想法来想。什么是贪心？就是“只要现在有机会，就立刻把花种下去，绝不犹豫”。因为种花这个事，越早种下，越可能给后面的花腾出更多空间。

但是，怎么判断“现在有机会”呢？我们得像个侦探一样，根据当前格子的情况，决定下一步怎么走。我们可以把整个过程想象成在花坛里“跳格子”，每一步都做出一个聪明的决定。

核心思想是：我们不需要检查每一个格子。 因为规则很严格，一旦某个格子确定了，它周围的格子命运也就定了。我们可以利用这一点，一次跳过好几个格子，大大加快速度。

具体怎么跳呢？我们站在当前格子 i 上，看看它是什么情况：

1. 情况一：当前格子已经有花了（`flowerbed[i] == 1`）

• 那很简单，根据规则，它右边的格子（i+1）肯定不能种花了。所以，我们完全没必要去看 i+1 这个格子了。
• 我们的行动： 直接跳过它，从 i+2 开始继续看。这就是代码里 i += 2 的原因。

2. 情况二：当前格子是空的（`flowerbed[i] == 0`）

• 这就有机会了！但能不能种，还得看它右边的邻居。
• 子情况 A：右边邻居也是空的（`flowerbed[i+1] == 0`），或者当前格子已经是最后一个了（`i == flowerbed.length - 1`）
• 太好了！这意味着当前格子可以种花。我们立刻种下（n--）。
• 种下之后，根据规则，它右边的格子（i+1）肯定不能种了。所以，我们又可以跳过 i+1，从 i+2 开始继续看。
• 我们的行动： 种花，然后 i += 2。

• 子情况 B：右边邻居已经有花了（`flowerbed[i+1] == 1`）
• 糟糕，当前格子不能种花了，因为它右边有花。
• 那下一步看哪里呢？i+1 有花，肯定不能种。i+2 呢？因为 i+1 有花，所以 i+2 也不能种（它们相邻）。所以，i、i+1、i+2 这三个格子我们都不用再看了。
• 我们的行动： 直接跳过这三个格子，从 i+3 开始继续看。这就是代码里 i += 3 的原因。

你看，通过这三种情况，我们就像在花坛里玩一个“跳格子”游戏，每次都能聪明地跳过那些“无用”的格子，只检查真正有可能种花的位置。这就是贪心算法的魅力：在局部做出最优选择（能种就种），从而得到全局最优解（种下最多的花）。

---

代码逐步拆解

现在，我们对照着参考代码，一步步来看它是怎么实现的。

class Solution {
   public boolean canPlaceFlowers(int[] flowerbed, int n) {
       // 1. 开始“跳格子”游戏
       // 循环条件：i 还没跳出花坛，并且我们还有花要种（n > 0）
       for( int i = 0 ; i < flowerbed.length && n > 0 ;){

           // 2. 情况一：当前格子已经有花了
           if(flowerbed[i] == 1){
               // 直接跳过它和它的右边邻居，从 i+2 开始看
               i += 2;

           // 3. 情况二：当前格子是空的
           // 并且，要么它是最后一个格子，要么它的右边邻居也是空的
           }else if(i == flowerbed.length - 1 || flowerbed[i + 1] == 0){
               // 可以种花！种下一朵，n 减 1