题目
解法1：二分判定+sliding window
由于所求的这个最大长度一定唯一而且会在连续的整数中产生，所以可以用二分判定
- 选取一个特定长度，判断是否存在特定长度的subarray符合条件
- 对于每次判定，使用sliding window的方法，所以每次判定复杂度O(n)
- 总的复杂度O(nlogn)
class Solution:def longestSubarray(self, nums: List[int], limit: int) -> int:n = len(nums)def clean_deq_max(i,mid,deq_max):if deq_max and deq_max[0]==i-mid:deq_max.popleft()# 去除队尾比新元素小的值的indexwhile deq_max and nums[i]>nums[deq_max[-1]]:deq_max.pop()def clean_deq_min(i,mid,deq_min):if deq_min and deq_min[0]==i-mid:deq_min.popleft()# 去除队尾比新元素小的值的indexwhile deq_min and nums[i]<nums[deq_min[-1]]:deq_min.pop()def check(mid):deq_max = collections.deque()deq_min = collections.deque()for i in range(mid):clean_deq_max(i,mid,deq_max)deq_max.append(i)clean_deq_min(i,mid,deq_min)deq_min.append(i)curr_max = nums[deq_max[0]]curr_min = nums[deq_min[0]]#print(curr_max,curr_min)if curr_max-curr_min <= limit:return Truefor i in range(mid,n):clean_deq_max(i,mid,deq_max)deq_max.append(i)curr_max = nums[deq_max[0]]clean_deq_min(i,mid,deq_min)deq_min.append(i)curr_min = nums[deq_min[0]]#print(curr_max,curr_min)if curr_max - curr_min <= limit:return Truereturn False#check(3)lo, hi = 0, len(nums)while lo+1<hi:mid = lo + (hi-lo)//2#print(mid)if check(mid):lo = midelse:hi = midif check(hi):return hielse:return lo
sliding window的做法可以参考这边
这种方法事实证明很慢,写起来也复杂，看到别人有写了O(n)的解法，见解法2
解法2：two pointers + sliding window
这里更加机智地采用了变长的sliding window方法，详细解释见代码注释
class Solution:def longestSubarray(self, nums: List[int], limit: int) -> int:# use two point with sliding window maximum & minimum. The sliding window here with variable length (unlike traditional sliding window)n = len(nums)# minQ keeps the minimum value in current window minQ = collections.deque()# maxQ keeps the maximum value in current windowmaxQ = collections.deque()# initialize the left and right pointer at the begining of the arrayl = r = 0res = 0while r<n:# if the current is empty or the new coming number from right won't change the largest absolute difference between any two elements of current windowif l==r or (nums[r]-minQ[0]<=limit and maxQ[0]-nums[r]<=limit):# clear the minQwhile minQ and minQ[-1]>nums[r]:minQ.pop()# clear the maxQwhile maxQ and maxQ[-1]<nums[r]:maxQ.pop()# extend the new number to minQ and maxQminQ.append(nums[r])maxQ.append(nums[r])# move the right pointerr += 1 # update the resultres = max(res,r-l)# else, the current window is not valid any more, we need to move the left pointer to find a new valid subarray. Because if we further extend the right pointer, the absolute difference will only be larger than current windowelse:# if the current left element is the min or max value of current window, we need to first pop out this valueif nums[l] == minQ[0]:minQ.popleft()if nums[l] == maxQ[0]:maxQ.popleft()# move the left pointl += 1return res