TreeMap 的做法 O(nlogn)
单调队列的做法 O(n)
前置题:剑指 Offer 59 - II. 队列的最大值
class Solution {
public int longestSubarray(int[] nums, int limit) {
// 滑动窗口/队列的最值
// 单调队列:维护当前队列的最小值和最大值
// minDeque:只要我后来的比前面的小,你就永无出头之日(相等要保留,出队时用),所以是非严格单调递增
// maxDeque:只要我后来的比前面的大,你就永无出头之日(相等要保留,出队时用),所以是非严格单调递减
int res = 0;
Deque<Integer> minDeque = new ArrayDeque<>();
Deque<Integer> maxDeque = new ArrayDeque<>();
// 对于每一个 i 求最靠左的 j,使得最大值 - 最小值 <= limit
// 单调性
for (int i = 0, j = 0; i < nums.length; i++) {
while (!minDeque.isEmpty() && minDeque.peekLast() > nums[i]) minDeque.pollLast();
minDeque.addLast(nums[i]);
while (!maxDeque.isEmpty() && maxDeque.peekLast() < nums[i]) maxDeque.pollLast();
maxDeque.addLast(nums[i]);
while (maxDeque.peekFirst() - minDeque.peekFirst() > limit) {
if (nums[j] == maxDeque.peekFirst()) maxDeque.pollFirst();
if (nums[j++] == minDeque.peekFirst()) minDeque.pollFirst();
}
res = Math.max(res, i - j + 1);
}
return res;
}
}
时间复杂度:每个元素最多入队一次出队一次,所以时间复杂度是 O(n) 的