Untitled
unknown
plain_text
a year ago
1.6 kB
4
Indexable
class Solution {
public long continuousSubarrays(int[] nums) {
Deque<Integer> maxDeque = new LinkedList<>();
Deque<Integer> minDeque = new LinkedList<>();
int i = 0, j = 0; // Sliding window pointers
int maxLength = 0;
long count = 0;
while (j < nums.length) {
// Maintain max deque
while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] < nums[j]) {
maxDeque.pollLast();
}
maxDeque.offerLast(j);
// Maintain min deque
while (!minDeque.isEmpty() && nums[minDeque.peekLast()] > nums[j]) {
minDeque.pollLast();
}
minDeque.offerLast(j);
// Check if the current window satisfies the condition
while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2) {
i = Math.min(minDeque.peekFirst(), maxDeque.peekFirst()) + 1;
// Prune irrelevant indices
while (!maxDeque.isEmpty() && maxDeque.peekFirst() < i) {
maxDeque.pollFirst();
}
while (!minDeque.isEmpty() && minDeque.peekFirst() < i) {
minDeque.pollFirst();
}
}
// for the valid window , subarrys ending at j pattern
count+= j - i + 1;
// Update the maximum length of the window
// maxLength = Math.max(maxLength, j - i + 1);
j++;
}
return count;
}
}Editor is loading...
Leave a Comment