标签: 数组
难度: Easy
给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 True ；否则，返回 False 。
示例 1：
输入：nums = [1,0,0,0,1,0,0,1], k = 2 输出：true 解释：每个 1 都至少相隔 2 个元素。
示例 2：
输入：nums = [1,0,0,1,0,1], k = 2 输出：false 解释：第二个 1 和第三个 1 之间只隔了 1 个元素。
示例 3：
输入：nums = [1,1,1,1,1], k = 0 输出：true
示例 4：
输入：nums = [0,1,0,1], k = 1 输出：true
提示：
1 <= nums.length <= 10^50 <= k <= nums.lengthnums[i] 的值为 0 或 1运行时间: 38 ms
内存: 19.2 MB
class Solution:
def kLengthApart(self, nums: List[int], k: int) -> bool:
p = -1
for i, num in enumerate(nums):
if num == 1:
if p == -1:
p = i
elif i - p <= k:
return False
else:
p = i
return True
这道题解的思路是遍历数组，使用一个变量p来记录上一个1的位置。初始时，p设为-1，表示还没有遇到1。遍历数组时，如果遇到1，首先检查p是否为-1，如果是，说明这是第一个1，更新p为当前位置i。如果不是，说明之前已经遇到过1，此时需要检查当前1的位置i和上一个1的位置p之间的距离是否大于k。如果不大于k，则说明存在相邻的1没有满足条件，直接返回False。如果大于k，则更新p为当前位置i。遍历结束后，如果没有返回False，则说明所有1都满足条件，返回True。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def kLengthApart(self, nums: List[int], k: int) -> bool:
p = -1 # 初始化上一个1的位置为-1
for i, num in enumerate(nums): # 遍历数组
if num == 1: # 如果遇到1
if p == -1: # 如果这是第一个1
p = i # 更新p为当前位置
elif i - p <= k: # 如果当前1和上一个1的距离不大于k
return False # 返回False
else: # 如果当前1和上一个1的距离大于k
p = i # 更新p为当前位置
return True # 遍历结束，返回True
将变量p初始化为-1是为了区分数组中的第一个1与之后遇到的1。如果p初始化为0，那么在数组开头就是1的情况下，算法会错误地认为第一个位置（索引0）之前已有一个1，这会导致逻辑错误。初始化p为-1可以让我们在遇到第一个1时，正确地将其位置设置为索引，而不进行不必要的距离比较。
是的，算法仍然可以正确工作。如果数组中只有一个1，p在遇到这个1时会从-1更新为该1的位置，之后没有更多的1来触发距离检查，因此算法会返回True。如果数组中没有1，那么p将始终为-1，循环结束后同样返回True，因为不存在不满足条件的相邻1的情况。
使用小于等于（`<=`）是为了确保两个1之间的元素数量至少有k个。如果使用了严格小于（`<`），则允许的间隔会变成k+1个元素，这与题目要求的至少k个元素间隔不符。等号确保了两个1之间的距离刚好可以是k，符合题目要求。
该算法已经考虑了包括连续1在内的所有情况。当遇到连续的1时（即没有间隔或间隔小于k），算法会通过`i - p <= k`的条件检查来判断这些1是否符合要求。如果不符合，算法会立即返回False。因此，连续的1或任何不满足间隔要求的情况都会被正确处理。