Untitled

 avatar
unknown
plain_text
a month ago
1.6 kB
0
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;
    }
}
Leave a Comment