class Solution:

    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:

        from collections import OrderedDict

        n = len(nums)

        if n <= 1 or k < 1 or t < 0: return False

        queue = OrderedDict()

        for n in nums:

            key = n if not t else n // t

            for m in [queue.get(key-1), queue.get(key), queue.get(key+1)]:

                if m is not None and abs(n - m) <= t:

                    return True

            if len(queue) == k:

                queue.popitem(False)

            queue[key] = n

        return False

def containsNearbyAlmostDuplicate(self, nums, k, t):

    if t < 0: return False

    n = len(nums)

    d = {}

    w = t + 1

    for i in range(n):

        m = nums[i] // w

        if m in d:

            return True

        if m - 1 in d and abs(nums[i] - d[m - 1]) < w:

            return True

        if m + 1 in d and abs(nums[i] - d[m + 1]) < w:

            return True

        d[m] = nums[i]

        if i >= k: del d[nums[i - k] // w]

    return False