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

Link

Solution

The logic is to find the max and min of subarray and check the diff (max-min) to see if it is satisfied.

About how to max and min, we can use Deque to tracing the possible value

1. So we kept a deque to store all min candidates which the frontest one is the min so far, and the element behind is the other candidate with accending order.

2. When we iterate nums[i], we have to know that for each num[k], where k < i && num[k] > num[i], num[k] can't be the min, for all subarray which end is i

3. When we decrease the start index, we check if num[start] is the min by far, if yes, we remove it from the deque and find the next frontest is the new min

4. Do the same thing to obtain the max

  public int longestSubarray(int[] nums, int limit) {
        int count = 0;
        Deque<Integer> min = new ArrayDeque<>();
        Deque<Integer> max = new ArrayDeque<>();
        int i = 0;
        for(int j = 0; j < nums.length; j++){
            while(!min.isEmpty() && min.peekLast() > nums[j]) min.pollLast();
            while(!max.isEmpty() && max.peekLast() < nums[j]) max.pollLast();
            max.add(nums[j]);
            min.add(nums[j]);
            while(max.peek() - min.peek() > limit){
                if(nums[i] == max.peek()){
                    max.poll();
                }
                if(nums[i] == min.peek()){
                    min.poll();
                }
                i++;
            }
            count = Math.max(count, j-i+1);
        }
        return count;
        
    }