1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (mono deque)

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

经典啊，用treemap也能做但是没有mono deque快，mono deque能维护一个sliding window内的最大值或最小值

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        // mono increase deque
        Deque<Integer> iq = new ArrayDeque<>();
        // mono decrease deque
        Deque<Integer> dq = new ArrayDeque<>();
        int i = 0;
        int maxLen = 0;
        for (int j = 0; j < nums.length; j++) {
            while (!iq.isEmpty() && nums[iq.peekLast()] > nums[j]) {
                iq.pollLast();
            }
            iq.offer(j);
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[j]) {
                dq.pollLast();
            }
            dq.offer(j);
            
            int maxVal = nums[dq.peek()];
            int minVal = nums[iq.peek()];
            while (maxVal - minVal > limit) {
                i++;
                if (dq.peek() < i) {
                    dq.poll();
                }
                if (iq.peek() < i) {
                    iq.poll();
                }
                maxVal = nums[dq.peek()];
                minVal = nums[iq.peek()];
            }
            maxLen = Math.max(maxLen, j-i+1);
        }
        return maxLen;
    }
}