-
Notifications
You must be signed in to change notification settings - Fork 2
/
LongestSubarrayWithAbsoluteDifferenceLessThanLimit.java
97 lines (82 loc) · 2.8 KB
/
LongestSubarrayWithAbsoluteDifferenceLessThanLimit.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package Leetcode;
import java.util.Deque;
import java.util.LinkedList;
/**
* @author kalpak
*
* Given an array of integers nums and an integer limit,
* return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
*
*
* 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^5
* 1 <= nums[i] <= 10^9
* 0 <= limit <= 10^9
*
*/
public class LongestSubarrayWithAbsoluteDifferenceLessThanLimit {
public static int longestSubarray(int[] nums, int limit) {
Deque<Integer> maxDeque = new LinkedList<>();
Deque<Integer> minDeque = new LinkedList<>();
int result = 1;
int i = 0;
// find the longest subarray for every right pointer by shrinking left pointer
for (int j = 0; j < nums.length; j++) {
// update maxDeque with new right pointer
while (!maxDeque.isEmpty() && maxDeque.peekLast() < nums[j]) {
maxDeque.removeLast();
}
maxDeque.addLast(nums[j]);
// update minDeque with new right pointer
while (!minDeque.isEmpty() && minDeque.peekLast() > nums[j]) {
minDeque.removeLast();
}
minDeque.addLast(nums[j]);
// shrink left pointer if exceed limit
while (maxDeque.peekFirst() - minDeque.peekFirst() > limit) {
if (maxDeque.peekFirst() == nums[i])
maxDeque.pollFirst();
if (minDeque.peekFirst() == nums[i])
minDeque.pollFirst();
i++; // shrink it!
}
// update res
result = Math.max(result, j - i + 1);
}
return result;
}
public static void main(String[] args) {
int[] arr = new int[]{4,2,2,2,4,4,2,2};
System.out.println(longestSubarray(arr, 0));
}
}