1437. 是否所有 1 都至少相隔 k 个元素

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given an binary array nums and an integer k, return true if all1 _' s are at least _k places away from each other, otherwise returnfalse.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2

Output: true

Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2

Output: false

Explanation: The second 1 and third 1 are only one apart from each other.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= k <= nums.length
• nums[i] is 0 or 1

题目大意

给你一个由若干 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 个元素。

提示：

• 1 <= nums.length <= 10^5
• 0 <= k <= nums.length
• nums[i] 的值为 0 或 1

解题思路

可以通过遍历数组并记录上一个 1 出现的位置来实现。

1. 用 prevOne 记录上一次出现 1 的位置，初始值设置为 -k-1，确保第一次出现 1 时不会误判。

2. 遍历数组:

   • 如果当前元素是 1，检查当前位置与 prevOne 的差值是否小于等于 k。
     • 如果小于或等于 k，返回 false。
   • 更新 prevOne 为当前的索引值。

3. 遍历结束后，如果所有的 1 间隔都符合要求，返回 true。

复杂度分析

• 时间复杂度: O(n)，需要遍历整个数组，每个元素只访问一次。
• 空间复杂度: O(1)，只使用了常数额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var kLengthApart = function (nums, k) {
	let prevOne = -k - 1; // 确保第一个 1 不会误判
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] === 1) {
			if (i - prevOne <= k) {
				return false; // 距离不足
			}
			prevOne = i; // 更新上一次出现 1 的位置
		}
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
2365	任务调度器 II		数组 哈希表 模拟	🟠	🀄️ 🔗