1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
class Solution {
public int longestSubarray(int[] nums, int limit) {
TreeMap<Integer, Deque<Integer>> map = new TreeMap<>();
int ans = 0;
int i = 0;
int j = 0;
while (j < nums.length) {
Deque<Integer> indexes = map.get(nums[j]);
if (indexes == null) {
indexes = new ArrayDeque<>();
}
if (indexes.isEmpty() || indexes.peekLast() != j) {
indexes.offerLast(j);
map.put(nums[j], indexes);
}
int max = map.lastKey();
int min = map.firstKey();
if (max - min > limit) {
Deque<Integer> iIndexes = map.get(nums[i]);
iIndexes.pollFirst();
if (iIndexes.size() == 0) {
map.remove(nums[i]);
} else {
map.put(nums[i], iIndexes);
}
i++;
} else {
ans = Math.max(ans, j - i + 1);
j++;
}
}
return ans;
}
}
sliding window + treemap + deque,之所以可以用sliding window是因为它要求区间里任意两对数的diff不超过limit,因此只要区间不满足条件左指针就可以往前移动,然后就是用treemap来维护区间里面的最大值和最小值以及对应坐标们,坐标似乎也不用deque来存?
Last updated