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.
1#include <deque>
2#include <vector>
3using namespace std;
4
5int longestSubarray(vector<int>& nums, int limit) {
6 deque<int> minDeque, maxDeque;
7 int left = 0, maxLength = 0;
8
9 for (int right = 0; right < nums.size(); ++right) {
10 while (!minDeque.empty() && nums[minDeque.back()] > nums[right])
11 minDeque.pop_back();
12 while (!maxDeque.empty() && nums[maxDeque.back()] < nums[right])
maxDeque.pop_back();
minDeque.push_back(right);
maxDeque.push_back(right);
while (nums[maxDeque.front()] - nums[minDeque.front()] > limit) {
++left;
if (minDeque.front() < left) minDeque.pop_front();
if (maxDeque.front() < left) maxDeque.pop_front();
}
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}This C++ version follows the same logic as described. It utilizes STL's deque to maintain the order of indices corresponding to minimum and maximum values in the current window range.
On breach of the limit condition, the left pointer slides forward to adjust the size of the window while checking and maintaining the elements in the deques.
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.