Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
MediumArrayQueueSliding WindowHeap (Priority Queue)Ordered SetMonotonic Queue
Solution
export function longestSubarray(nums: number[], limit: number): number {
const minDeque: number[] = [];
const maxDeque: number[] = [];
let answer = 0;
let [left, right] = [0, 0];
while (right < nums.length) {
while (0 < minDeque.length && nums[right] <= nums[minDeque[minDeque.length - 1]]) {
minDeque.pop();
}
while (0 < maxDeque.length && nums[right] >= nums[maxDeque[maxDeque.length - 1]]) {
maxDeque.pop();
}
minDeque.push(right);
maxDeque.push(right);
while (limit < nums[maxDeque[0]] - nums[minDeque[0]]) {
left += 1;
if (minDeque[0] < left) {
minDeque.shift();
}
if (maxDeque[0] < left) {
maxDeque.shift();
}
}
answer = Math.max(answer, right - left + 1);
right += 1;
}
return answer;
}