1438. 絕對(duì)差不超過(guò)限制的最長(zhǎng)連續(xù)子數(shù)組
給你一個(gè)整數(shù)數(shù)組 nums 葬馋，和一個(gè)表示限制的整數(shù) limit卖鲤，請(qǐng)你返回最長(zhǎng)連續(xù)子數(shù)組的長(zhǎng)度，該子數(shù)組中的任意兩個(gè)元素之間的絕對(duì)差必須小于或者等于 limit 畴嘶。
如果不存在滿足條件的子數(shù)組蛋逾，則返回 0 。
示例 1：
輸入：nums = [8,2,4,7], limit = 4
輸出：2
解釋：所有子數(shù)組如下：
[8] 最大絕對(duì)差 |8-8| = 0 <= 4.
[8,2] 最大絕對(duì)差 |8-2| = 6 > 4.
[8,2,4] 最大絕對(duì)差 |8-2| = 6 > 4.
[8,2,4,7] 最大絕對(duì)差 |8-2| = 6 > 4.
[2] 最大絕對(duì)差 |2-2| = 0 <= 4.
[2,4] 最大絕對(duì)差 |2-4| = 2 <= 4.
[2,4,7] 最大絕對(duì)差 |2-7| = 5 > 4.
[4] 最大絕對(duì)差 |4-4| = 0 <= 4.
[4,7] 最大絕對(duì)差 |4-7| = 3 <= 4.
[7] 最大絕對(duì)差 |7-7| = 0 <= 4.
因此窗悯，滿足題意的最長(zhǎng)子數(shù)組的長(zhǎng)度為 2 区匣。
示例 2：
輸入：nums = [10,1,2,4,7,2], limit = 5
輸出：4
解釋：滿足題意的最長(zhǎng)子數(shù)組是 [2,4,7,2]，其最大絕對(duì)差 |2-7| = 5 <= 5 。
示例 3：
輸入：nums = [4,2,2,2,4,4,2,2], limit = 0
輸出：3
題解：
題目要求子數(shù)組中的任意兩個(gè)元素之間的絕對(duì)差必須小于或者等于 limit亏钩，也就是說(shuō)：這個(gè)子數(shù)組中的最大值-最小值的值要小于等于limit莲绰。因此我維護(hù)了兩個(gè)優(yōu)先隊(duì)列，一個(gè)是大根堆姑丑，一個(gè)是小根堆蛤签，這樣我們就能輕松獲取到子數(shù)組中的最大值和最小值。接下來(lái)栅哀，就可以使用滑動(dòng)窗口的模板了震肮。需要注意的是，在窗口滑動(dòng)時(shí)留拾，要記得更新優(yōu)先隊(duì)列戳晌。
public int longestSubarray(int[] nums, int limit) {
if (nums == null || nums.length < 0) return 0;
PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.naturalOrder()); //小根堆
PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder()); //大根堆
int n = nums.length;
int left = 0;
int right = 0;
int ans = 0;
while (right < n) {
minQueue.add(nums[right]);
maxQueue.add(nums[right]);
while (maxQueue.peek() - minQueue.peek() > limit) {
if (!maxQueue.isEmpty()) {
maxQueue.remove(nums[left]);
}
if (!minQueue.isEmpty()) {
minQueue.remove(nums[left]);
}
left++;
}
ans = Math.max(ans, right - left + 1);
right++;
}
return ans;
}
還有另外一種數(shù)據(jù)結(jié)構(gòu)：TreeMap。TreeMap 是 key 有序的哈希表痴柔，它是基于紅黑樹(shù)實(shí)現(xiàn)的沦偎。除此之外，它還提供了獲取第一個(gè)元素(最小值)和最后一個(gè)元素(最大值)的函數(shù)咳蔚，因此代碼更加簡(jiǎn)潔豪嚎。詳細(xì)請(qǐng)參考這位大佬
public int longestSubarray(int[] nums, int limit) {
TreeMap<Integer, Integer> m = new TreeMap<>();
int left = 0, right = 0;
int res = 0;
while (right < nums.length) {
m.put(nums[right], m.getOrDefault(nums[right], 0) + 1);
while (m.lastKey() - m.firstKey() > limit) {
m.put(nums[left], m.get(nums[left]) - 1);
if (m.get(nums[left]) == 0) {
m.remove(nums[left]);
}
left ++;
}
res = Math.max(res, right - left + 1);
right ++;
}
return res;
}
