LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.17
• 题目：1437.是否所有1都至少相隔k个元素
• 难度：中等
• 标签: 数组 贪心

1. 题目理解

问题描述：
给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 true ；否则，返回 false 。

示例：

输入：nums = [1,0,0,0,1,0,0,1], k = 2 输出：true 解释：每个 1 都至少相隔 2 个元素。

输入：nums = [1,0,0,1,0,1], k = 2 输出：false 解释：第二个 1 和第三个 1 之间只隔了 1 个元素，不满足要求。

2. 解题思路

核心观察

要判断所有 1 之间的距离是否≥k，只需记录上一个 1 的位置，然后遍历数组，每次遇到新的 1 时计算与上一个 1 的距离即可。

算法步骤

1. 初始化 lastOneIndex = -1（表示还未遇到第一个 1）。
2. 遍历数组 nums：
   • 若当前元素是 1：
     • 如果是第一个 1（lastOneIndex == -1），仅更新 lastOneIndex 为当前索引。
     • 否则，计算当前 1 与上一个 1 的距离 distance = 当前索引 - lastOneIndex - 1（减1是因为要排除两个 1 本身，只统计中间的 0 数量）。
     • 若 distance < k，直接返回 false。
     • 否则，更新 lastOneIndex 为当前索引。
3. 遍历结束后，返回 true（所有 1 之间的距离都满足要求）。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int n = nums.length;
        int lastOneIndex = -1; 
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                if (lastOneIndex != -1) {
                    int distance = i - lastOneIndex - 1; 
                    if (distance < k) {
                        return false;
                    }
                }
                lastOneIndex = i; 
            }
        }
        return true;
    }
}

4. 代码优化说明

• 时间复杂度优化：只需遍历一次数组，时间复杂度为 O(n)（n 是数组长度），已是最优。
• 空间复杂度优化：仅用常数级额外空间（lastOneIndex 和循环变量），空间复杂度为 O(1)，无优化空间。

5. 复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。只需遍历数组一次，每个元素最多被访问一次。
• 空间复杂度：O(1)，仅使用了常数个额外变量（lastOneIndex、n、i、distance）。

6. 总结

本题的核心是通过记录上一个 1 的位置，线性遍历判断所有 1 之间的距离。算法逻辑清晰，时间和空间复杂度均为最优，是典型的“贪心”思路在数组问题中的应用——每次遇到 1 就立即判断是否满足条件，一旦不满足直接返回结果，避免了不必要的计算。

这类“相邻元素约束”的问题，通常都可以通过记录前一个满足条件的位置来线性解决，是数组类题目中的常见解题范式。