1438. 绝对差不超过限制的最长连续子数组 #

标签：队列、数组、有序集合、滑动窗口、单调队列、堆（优先队列）
难度：中等

题目大意 #

给定一个整数数组 nums，和一个表示限制的整数 limit。

要求：返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。

如果不存在满足条件的子数组，则返回 0。

解题思路 #

求最长连续子数组，可以使用滑动窗口来解决。这道题目的难点在于如何维护滑动窗口内的最大值和最小值的差值。遍历滑动窗口求最大值和最小值，每次计算的时间复杂度为 $O(k)$，时间复杂度过高。考虑使用特殊的数据结构来降低时间复杂度。可以使用堆（优先队列）来解决。这里使用 Python 中 heapq 实现。具体做法如下：

使用 left、right 两个指针，分别指向滑动窗口的左右边界，保证窗口中最大值和最小值的差值不超过 limit。
一开始，left、right 都指向 0。
向右移动 right，将最右侧元素加入当前窗口和大顶堆、小顶堆中。
如果大顶堆堆顶元素和小顶堆堆顶元素大于 limit，则不断右移 left，缩小滑动窗口长度，并更新窗口内的大顶堆、小顶堆。
如果大顶堆堆顶元素和小顶堆堆顶元素小于等于 limit，则更新最长连续子数组长度。
然后继续右移 right，直到 right >= len(nums) 结束。
输出答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import heapq

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        size = len(nums)
        heap_max = []
        heap_min = []

        ans = 0
        left, right = 0, 0
        while right < size:
            heapq.heappush(heap_max, [-nums[right], right])
            heapq.heappush(heap_min, [nums[right], right])

            while -heap_max[0][0] - heap_min[0][0] > limit:
                while heap_min[0][1] <= left:
                    heapq.heappop(heap_min)
                while heap_max[0][1] <= left:
                    heapq.heappop(heap_max)
                left += 1
            ans = max(ans, right - left + 1)
            right += 1

        return ans