Untitled
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