题目信息

题目描述

给定一个只包含 0/1 的数组
ums 和整数 k，判断任意两个 1 之间的间隔（指两个 1 的索引差减 1）是否都至少为 k。

初步思路

  1. 从左到右扫描数组，记录上一个 1 出现的位置 last1。
  2. 每遇到一个新的 1，检查与 last1 之间的间隔是否小于 k，若是则返回 alse。
  3. 否则更新 last1，继续扫描，最后返回 rue。

算法分析

  • 核心：一次遍历 + 记录最近的 1。
  • 技巧：可以将 last1 初始化为一个足够小的值（例如 -inf 或 -k-1），这样第一次遇到 1 时无需特判。
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码实现（Python）

from math import inf
from typing import List

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        last1 = -inf
        for index, num in enumerate(nums):
            if num != 1:
                continue
            if index - last1 - 1 < k:
                return False
            last1 = index
        return True

测试用例

输入 输出 说明
nums = [1,0,0,0,1,0,0,1], k = 2 false 后两个 1 间隔不足 2
nums = [1,0,0,0,1,0,0,0], k = 2 true 所有 1 间隔均≥2
nums = [0,0,0], k = 1 true 无 1，自然满足

总结与反思

  1. 典型的双指针问题，一个指针记录上一个 1 出现的位置，一个指针遍历数组。