14. Remove Elements Within K Distance

Origin: Remove Elements Within K Distance

Given a non-decreasing array of integers and an integer K, remove in-place any element that is within K of the previous kept element and return the new length. Use constant extra space and single pass with two pointers.

Example

Input: timestamps = [1, 2, 3, 8, 10] K = 3

Output: 2

Explanation:

• We start by keeping the first timestamp 1.
• Next, 2 - 1 = 1 < 3, so 2 is removed.
• Next, 3 - 1 = 2 < 3, so 3 is removed.
• Next, 8 - 1 = 7 >= 3, so we keep 8.
• Finally, 10 - 8 = 2 < 3, so 10 is removed.
• The remaining timestamps are [1, 8], so the new length is 2.

Input Format

• First line contains two space-separated integers N and K, where 0 <= N <= 1000 and 0 <= K <= 10
• Second line contains N space-separated integers timestamps[0..N-1], each satisfying 0 <= timestamps[i] <= 10^9 and the sequence is non-decreasing.

Constraints

• 0 <= timestamps.length <= 1000
• 0 <= timestamps[i] <= 10^9 for all 0 <= i < timestamps.length
• timestamps[i] <= timestamps[i+1] for all 0 <= i < timestamps.length - 1
• 0 <= K <= 10

Output Format

A single integer L, representing the new length of the timestamps array after retaining only those timestamps that are at least K seconds apart from the previous kept timestamp.

Sample Input 0

0 10

Sample Output 0

0

Sample Input 1

1 5
0

Sample Output 1

1

---

函数契约

// 输入：timestamps（非递减整数数组），K（间隔阈值）
// 输出：新长度（整数），保留的元素和上一个保留元素差值 >= K
// 边界：空数组 → 0；单元素 → 1；全部间隔 < K → 1

边界表

场景	返回什么
空数组	0
单元素	1
全部间隔 < K	1（只保留第一个）
全部间隔 >= K	n（全部保留）
正常场景	计数

Resolution

我的解法

function debounceTimestamps(timestamps: number[], K: number): number {
    let count = 0
    let per = 0
    let cur = 1
 
    if (timestamps.length === 0) return 0
    if (timestamps.length === 1) return 1
    while (cur < timestamps.length) {
        if (timestamps[cur] - timestamps[per] < K) {
            count++
        } else {
            per = cur
        }
        cur++
    }
 
    return timestamps.length - count
}

解题思路

双指针，per 指向”上一个保留的元素”，cur 遍历数组。

• 如果 timestamps[cur] - timestamps[per] < K，当前元素和上一个保留元素距离不够，移除，per 不动
• 否则保留当前元素，per 移到 cur

关键点：per 只在保留元素时才前进，不是每轮都前进。第一版代码的错误就是 per 和 cur 同步前进，变成了和相邻元素比较，而不是和上一个保留元素比较。

返回值是新长度 = 原长度 - 移除数量。

复杂度

• 时间：O(n)，一次遍历
• 空间：O(1)，两个指针 + 一个计数器

踩坑经历

第一版代码 per = cur - 1，每轮都移动 per，变成了相邻元素比较。正确做法是移除时 per 不动，保留时 per = cur。

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：12. Remove Consecutive Duplicates from Sorted Linked List — 类似的”跳过不符合条件的元素”思路