Untitled
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; } }
Leave a Comment