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

Explanation:

To solve this problem, we can use a sliding window approach. We would maintain two monotonic queues (one for maximum values and one for minimum values) to keep track of the maximum and minimum elements in the current window. By doing this, we can efficiently determine if the absolute difference between the minimum and maximum elements in the current window is less than or equal to the given limit.

1. Initialize two Deques (Double-ended queues) to store the maximum and minimum values in the current window.
2. Iterate through the array, maintaining the sliding window.
3. At each step, pop elements from the front of the Deques if they are outside the current window.
4. Add the current element to the end of both Deques.
5. Update the result by comparing the size of the current window with the longest window found so far.
6. Repeat until we have traversed the entire array.
7. Return the size of the longest subarray found.

Time Complexity: O(N), where N is the number of elements in the input array. Space Complexity: O(N), where N is the number of elements in the input array.

import java.util.ArrayDeque;

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        ArrayDeque<Integer> maxDeque = new ArrayDeque<>();
        ArrayDeque<Integer> minDeque = new ArrayDeque<>();
        int left = 0, right = 0;
        int longest = 0;

        for (; right < nums.length; right++) {
            while (!maxDeque.isEmpty() && nums[right] > maxDeque.peekLast()) {
                maxDeque.pollLast();
            }
            while (!minDeque.isEmpty() && nums[right] < minDeque.peekLast()) {
                minDeque.pollLast();
            }

            maxDeque.offerLast(nums[right]);
            minDeque.offerLast(nums[right]);

            if (maxDeque.peekFirst() - minDeque.peekFirst() > limit) {
                if (maxDeque.peekFirst() == nums[left]) maxDeque.pollFirst();
                if (minDeque.peekFirst() == nums[left]) minDeque.pollFirst();
                left++;
            }

            longest = Math.max(longest, right - left + 1);
        }

        return longest;
    }
}