1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

main 2 mono queue, one is max, one is min

T: O(n)

S: O(n)

class Solution {
    class MonoQueue {
        Deque<Integer> max = new ArrayDeque<>();
        Deque<Integer> min = new ArrayDeque<>();
        
        public void offer(int num) {
            while (!max.isEmpty() && num > max.getLast()) {
                max.pollLast();
            }
            max.offerLast(num);
            
            while (!min.isEmpty() && num < min.getLast()) {
                min.pollLast();
            }
            min.offerLast(num);
        }
        public void poll(int num) {
            if (max.getFirst() == num) {
                max.pollFirst();
            }
            if (min.getFirst() == num) {
                min.pollFirst();
            }
        }
        public int max() {
            return max.getFirst();
        }
        public int min() {
            return min.getFirst();
        }
    }
    
    public int longestSubarray(int[] nums, int limit) {
        MonoQueue window = new MonoQueue();
        int windowSize = 0;
        int result = 0;
        int left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            window.offer(nums[right]);
            windowSize++;
            while (window.max() - window.min() > limit) {
                window.poll(nums[left]);
                left++;
                windowSize--;
            }
            
            result = Math.max(result, windowSize);
        }
        return result;
    }
}

new version: Sliding win + monoQueue

```java
class Solution {
    private class MonoQueue {
        private Deque<Integer> minDeque;
        private Deque<Integer> maxDeque;

        MonoQueue() {
            minDeque = new ArrayDeque<>();
            maxDeque = new ArrayDeque<>();
        }
        public void offer(int num) {
            while (!maxDeque.isEmpty() && maxDeque.peekLast() < num) {
                maxDeque.pollLast();
            }
            maxDeque.offer(num);

            while (!minDeque.isEmpty() && minDeque.peekLast() > num) {
                minDeque.pollLast();
            }
            minDeque.offer(num);
        }
        public void poll(int num) {
            if (maxDeque.peekFirst() == num) {
                maxDeque.pollFirst();
            }
            if (minDeque.peekFirst() == num) {
                minDeque.pollFirst();
            }
        }
        public int getMax() {
            return maxDeque.peekFirst();
        }
        public int getMin() {
            return minDeque.peekFirst();
        }
    }
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        MonoQueue monoQueue = new MonoQueue();
        int result = 0;

        while (right < n) {
            int rightInt = nums[right];
            right++;
            monoQueue.offer(rightInt);
            
            while (monoQueue.getMax() - monoQueue.getMin() > limit) {
                int leftInt = nums[left];
                left++;
                monoQueue.poll(leftInt);
            }
            result = Math.max(result, right - left);
        }
        return result;
    }
}
```

latest one:

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        MinMaxMonoQueue queue = new MinMaxMonoQueue();

        int result = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            int rightNum = nums[right];
            queue.offer(rightNum);

            while (left < nums.length && queue.getMinMaxDiff() > limit) {
                int leftNum = nums[left];
                queue.poll(leftNum);
                left++;
            }
            result = Math.max(right - left + 1, result);
        }
        return result;
    }
    /**
    8 2 4 7
          r
        l
    limit = 8 - 8 = 0
    result = 1
    max[7]
    min[4, 7]
    8 - 2=  6 > limit
    l++
    result = 1;

4 - 2
result = 2 - 1 + 1 = 2
7 - 2 > 4 -> l++, poll 2
     */
    class MinMaxMonoQueue {
        Deque<Integer> max = new ArrayDeque<>();
        Deque<Integer> min = new ArrayDeque<>();

        public void offer(int num) {
            while (!max.isEmpty() && max.peekLast() < num) {
                max.pollLast();
            }
            max.offerLast(num);

            while (!min.isEmpty() && min.peekLast() > num) {
                min.pollLast();
            }
            min.offerLast(num);
        }
        public void poll(int num) {
            if (num == max.getFirst()) {
                max.pollFirst();
            }
            if (num == min.getFirst()) {
                min.pollFirst();
            }
        }
        public int getMax() {
            return max.getFirst();
        }
        public int getMin() {
            return min.getFirst();
        }
        public int getMinMaxDiff() {
            return Math.abs(getMax() - getMin());
        }
    }
}

/***
mono queue
T: O(n)
S: O(n)


8 2 4 7
      r
    l

10 1 2 4 7 2
           r
     l    

how to find max or min quickly? use monoqueue
 */