Untitled

 avatar
unknown
plain_text
a month ago
2.0 kB
1
Indexable
import java.util.Deque;
import java.util.LinkedList;

public class LongestSubarrayWithLimit {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();
        int i = 0, j = 0; // Sliding window pointers
        int maxLength = 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()] > limit) {
                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();
                }
            }

            // Update the maximum length of the window
            maxLength = Math.max(maxLength, j - i + 1);
            j++;
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubarrayWithLimit solution = new LongestSubarrayWithLimit();
        System.out.println(solution.longestSubarray(new int[]{8, 2, 4, 7}, 4)); // Output: 2
        System.out.println(solution.longestSubarray(new int[]{10, 1, 2, 4, 7, 2}, 5)); // Output: 4
        System.out.println(solution.longestSubarray(new int[]{4, 2, 2, 2, 4, 4, 2, 2}, 0)); // Output: 3
    }
}
Leave a Comment