Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1438.html
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Medium)
Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.
In case there is no subarray satisfying the given condition return 0.
Example 1:
Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2.
Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5 Output: 4 Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.
Example 3:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0 Output: 3
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
Related Topics:
Array, Sliding Window
Solution 1. Sliding Window
Use a multiset<int> s to keep track of the values within the window. We keep extending the right-hand side of the window indexed by j and add A[j] into s.
Whenever we find that the difference between max value and min value in s is greater than k, we shrink the window by moving the left-hand side of the window indexed by i. For every A[i] that we popped out from the window, we erase it from s as well.
In this way, we make sure the window is always valid. The maximum j - i is the answer.
// OJ: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int longestSubarray(vector<int>& A, int k) {
multiset<int> s{ A[0] };
int i = 0, j = 1, N = A.size(), ans = 1;
while (j < N) {
s.insert(A[j++]);
while (*s.rbegin() - *s.begin() > k) s.erase(s.find(A[i++]));
ans = max(ans, j - i);
}
return ans;
}
};
Solution 2. Monotonous Deque
We use monotonous deques to keep track of the max/min values within the window. See 239. Sliding Window Maximum (Hard) for the idea.
// OJ: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int longestSubarray(vector<int>& A, int k) {
deque<int> mx{A[0]}, mn{A[0]};
int N = A.size(), ans = 1, i = 0, j = 1;
while (j < N) {
while (j < N && mx.front() - mn.front() <= k) {
while (mx.size() && mx.back() < A[j]) mx.pop_back();
mx.push_back(A[j]);
while (mn.size() && mn.back() > A[j]) mn.pop_back();
mn.push_back(A[j]);
++j;
if (mx.front() - mn.front() <= k) ans = max(ans, j - i);
}
while (i < j && mx.front() - mn.front() > k) {
if (A[i] == mx.front()) mx.pop_front();
if (A[i] == mn.front()) mn.pop_front();
++i;
}
}
return ans;
}
};
Solution 3. Monotonous Deque
Similar to Solution 2, but since we are looking for the maximum window, we don’t shrink the window.
If the window is valid, we only increment the right edge.
Otherwise, we increment the left edge as well to shift the window as a whole.
// OJ: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC%2B%2BPython-Deques-O(N)
class Solution {
public:
int longestSubarray(vector<int>& A, int k) {
deque<int> mx, mn;
int i = 0, j = 0;
for (; j < A.size(); ++j) {
while (mx.size() && mx.back() < A[j]) mx.pop_back();
while (mn.size() && mn.back() > A[j]) mn.pop_back();
mx.push_back(A[j]);
mn.push_back(A[j]);
if (mx.front() - mn.front() > k) {
if (A[i] == mx.front()) mx.pop_front();
if (A[i] == mn.front()) mn.pop_front();
++i;
}
}
return j - i;
}
};
Java
-
class Solution { public int longestSubarray(int[] nums, int limit) { if (nums == null || nums.length == 0) return 0; int maxLength = 0; int start = 0; TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); int length = nums.length; for (int i = 0; i < length; i++) { int num = nums[i]; int count = map.getOrDefault(num, 0) + 1; map.put(num, count); while (map.lastKey() - map.firstKey() > limit) { int prevNum = nums[start]; int prevCount = map.get(prevNum) - 1; if (prevCount == 0) map.remove(prevNum); else map.put(prevNum, prevCount); start++; } maxLength = Math.max(maxLength, i - start + 1); } return maxLength; } } -
// OJ: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/ // Time: O(NlogN) // Space: O(N) class Solution { public: int longestSubarray(vector<int>& A, int k) { multiset<int> s{ A[0] }; int i = 0, j = 1, N = A.size(), ans = 1; while (j < N) { s.insert(A[j++]); while (*s.rbegin() - *s.begin() > k) s.erase(s.find(A[i++])); ans = max(ans, j - i); } return ans; } }; -
from sortedcontainers import SortedList class Solution: def longestSubarray(self, nums: List[int], limit: int) -> int: sl = SortedList() ans = j = 0 for i, v in enumerate(nums): sl.add(v) while sl[-1] - sl[0] > limit: sl.remove(nums[j]) j += 1 ans = max(ans, i - j + 1) return ans ############ class Solution(object): def longestSubarray(self, nums, limit): """ :type nums: List[int] :type limit: int :rtype: int """ N = len(nums) left, right = 0, 0 res = 0 visited = set() visited.add(nums[0]) while right < N: if (len(visited) != 1): max_ = max(nums[left : right + 1]) min_ = min(nums[left : right + 1]) cur = max_ - min_ else: cur = 0 if cur > limit: left += 1 else: visited.add(nums[right]) res = max(res, right - left + 1) right += 1 return res