```
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
deque<int> maxq, minq; // priority queue with max length k
for(int i = 0; i < nums.size(); ++i) {
while(!maxq.empty() && i - maxq.front() > k) maxq.pop_front(); // The greatest must also be the oldest. Otherwise it would have been popped from back
if(!maxq.empty() && abs((long long)nums[i] - nums[maxq.front()]) <= t) return true;
while(!minq.empty() && i - minq.front() > k) minq.pop_front(); // Pop the oldest
if(!minq.empty() && abs((long long)nums[i] - nums[minq.front()]) <= t) return true;
while(!maxq.empty() && nums[maxq.back()] <= nums[i]) maxq.pop_back();
maxq.push_back(i);
while(!minq.empty() && nums[minq.back()] >= nums[i]) minq.pop_back();
minq.push_back(i);
}
return false;
}
};
```

I use deque to maintain an increasing or decreasing queue whose maximum size is k. When the queue is too long, I remove the oldest element from the left. The increasing/decreasing characteristic assures that the left-most element must be the oldest. Otherwise it would have been popped from back.

Each nums[i] is compared against the max/min of the queue (i.e., the max/min of the last k elements)

Asymptotically each element is only pushed to or popped from the deque once, so the overall runtime is O(n)