Sponsored
Sponsored
This approach uses the sliding window technique along with two deques to efficiently keep track of the maximum and minimum values in the current window.
We maintain two deques - one for the indices of the maximum values and another for the minimum values, within the current window of the array, called `nums`. By utilizing the sliding window, we can dynamically adjust the start and end of the window based on whether the condition of the absolute difference being less than or equal to the limit is satisfied.
Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the deque at most once.
Space Complexity: O(n), due to the size of the deques which in the worst case can hold all elements.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestSubarray(int[] nums, int limit) {
6 var minDeque = new LinkedList<int>();
7 var maxDeque = new LinkedList<int>();
8 int left = 0;
9 int maxLength = 0;
10
11 for (int right = 0; right < nums.Length; right++) {
12 while (minDeque.Count != 0 && nums[minDeque.Last.Value] > nums[right])
minDeque.RemoveLast();
while (maxDeque.Count != 0 && nums[maxDeque.Last.Value] < nums[right])
maxDeque.RemoveLast();
minDeque.AddLast(right);
maxDeque.AddLast(right);
while (nums[maxDeque.First.Value] - nums[minDeque.First.Value] > limit) {
left++;
if (minDeque.First.Value < left)
minDeque.RemoveFirst();
if (maxDeque.First.Value < left)
maxDeque.RemoveFirst();
}
maxLength = Math.Max(maxLength, right - left + 1);
}
return maxLength;
}
}For the C# solution, we use LinkedList to practically implement the deque simulation, tracking minimum and maximum indices to evaluate window limitations correctly.
This approach uses a sliding window implemented with a TreeMap to automatically manage and get minimum and maximum values from the current window range.
Time Complexity: O(n log n); each insertion and deletion operation on TreeMap takes log n time.
Space Complexity: O(n); due to the additional space required by the TreeMap.
1import java.util.TreeMap;
2
3public
By leveraging the automatic ordering of keys within a TreeMap, this approach ensures the retrieval and conditional check of both minimum and maximum values within a determined window is efficient.
Upon the boundary violation concerning the permissible limit, the left pointer incrementally adjusts, pruning the TreeMap until the condition is restored.