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/

solution

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

• 双heap

# 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

时间复杂度：O() 空间复杂度：O()

• TreeMap

时间复杂度：O() 空间复杂度：O()

• 单调双端队列

时间复杂度：O() 空间复杂度：O()