描述:给定一个整数数组 nums,以及两个整数 k、t。
输出:True
这样在同一个桶内各个元素之间的差值绝对值都小于等于 t。而相邻桶之间的元素,只需要校验一下两个桶之间的差值是否不超过 t。这样就可以以 $O(1)$ 的时间复杂度检测相邻 2 * k 个元素是否满足 abs(nums[i] - nums[j]) <= t。
将每个桶的大小设置为 t + 1。我们将元素按照大小依次放入不同的桶中。
如果之前桶里没有元素,那么就将 nums[i] 放入对应桶中。
最后上述满足条件的情况就返回 True,最终遍历完仍不满足条件就返回 False。
使用有序数组类 window 维护一个长度为 k 的窗口,满足数组内元素有序,且支持增加和删除操作。
当窗口元素小于等于 k 个时:
重复 3 ~ 6 步,直到 right 到达数组末尾,如果还没找到满足条件的情况,则返回 False。
