LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit - 亚马逊高频题29

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

题目给定一个整型数组nums和一个整数limit，要求找到一个最长的子数组，使得该子数组中的任意两个数的差的绝对值都小于等于limit。

我们知道数组中任意两个数的差的绝对值的范围都不会超过数组中的最大值与最小值的差，因此我们只要关心子数组中的最大值和最小值，知道最大值与最小值的差不超过limit就符合题目要求。

本题的暴力解法就是，就是用两个循环找出从任意一个位置出发满足条件的所有最长子数组。

暴力解法的时间复杂度是O(n^2)会超时。

关于子数组的问题，最常用的一种解法就是移动窗口（Sliding Window）法。

所谓滑动窗口法就是用两个指针，一个指向窗口的左边另一个指向窗口的右边，从两个指针同时指向数组的第一个位置开始，为了使得窗口长度尽量长，右指针就要尽量的往右移动，在移动的过程维护窗口内的最大值和最小值，一旦最大值与最小值的差超过limit，右指针就要停止移动，这时的窗口长度减1就是当前满足条件的最长子数组。

这时就得开始移动左指针即把窗口左边数剔除，直到剔除掉了最大值或最小值使得窗口重新满足条件为止。

本题的难点在于，在移动左指针时如何知道何时剔除了最大值或最小值，又该如何知道窗口中新的最大值和最小值。

于是乎很自然的想到了最大堆和最小堆，在移动窗口的同时维护一个最大堆和最小堆（堆的元素是数组值和数组索引），那我们就可以快速地知道到任何时候窗口中的最大值和最小值的位置了。

在右指针每向右移动一步时，把当前位置的数值和索引放入最大堆和最小堆中，然后判断两个堆的顶部的数值差（即最大值与最小值的差）是否超过limit，如果超过说明此时需要移动窗口的左指针了，左指针至少要移动到窗口左边第一次出现最大值或最小值的下一个位置，由于两个堆同时也存放了索引号，因此可以快速知道左指针移动的下一个位置，在左指针移动到下个位置后，需要将最大堆和最小堆顶部且位置是在左指针新位置的左边的数从两个堆里移除（这里没必要把两个堆里的所有在左指针新位置左边的数移除，因此最大堆里的较小数和最小堆里的较大数都不影响结果）。

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxHeap, minHeap = [], []
        res = 1
        i = 0
        for j in range(len(nums)):
            heapq.heappush(maxHeap, (-nums[j], j))
            heapq.heappush(minHeap, (nums[j], j))
            if -maxHeap[0][0] - minHeap[0][0] > limit:
                i = min(maxHeap[0][1], minHeap[0][1]) + 1
                while maxHeap and maxHeap[0][1] < i:
                    heapq.heappop(maxHeap)
                while minHeap and minHeap[0][1] < i:
                    heapq.heappop(minHeap)
            res = max(res, j - i + 1)
        return res