class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
res = 1
for i in range(len(nums)):
max_heap = [-nums[i]] # 大堆，小堆保证新加入的不超过上限limit, 也不超过下限limit
min_heap = [nums[i]]
for j in range(i+1, len(nums)):
# 两个堆主要是方便确认limit
if abs(-max_heap[0] - nums[j]) <= limit and abs(min_heap[0] - nums[j]) <= limit:
heapq.heappush(max_heap, -nums[j])
heapq.heappush(min_heap, nums[j])
else:
break
res = max(res, len(max_heap))
return res
# https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
import heapq
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
max_length = 1
left = 0
min_heap = []
max_heap = []
for right in range(len(nums)):
heapq.heappush(min_heap, (nums[right], right))
heapq.heappush(max_heap, (-nums[right], right))
while min_heap[0][1] < left:
heapq.heappop(min_heap)
while max_heap[0][1] < left:
heapq.heappop(max_heap)
if -max_heap[0][0] - min_heap[0][0] <= limit:
max_length = max(max_length, right - left + 1)
else:
left += 1
return max_length