题目描述

给你一个整数数组 nums，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。

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

样例

输入：nums = [8,2,4,7], limit = 4
输出：2 
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4
[8,2] 最大绝对差 |8-2| = 6 > 4
[8,2,4] 最大绝对差 |8-2| = 6 > 4
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4
[2] 最大绝对差 |2-2| = 0 <= 4
[2,4] 最大绝对差 |2-4| = 2 <= 4
[2,4,7] 最大绝对差 |2-7| = 5 > 4
[4] 最大绝对差 |4-4| = 0 <= 4
[4,7] 最大绝对差 |4-7| = 3 <= 4
[7] 最大绝对差 |7-7| = 0 <= 4
因此，满足题意的最长子数组的长度为 2。

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4 
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5。

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

算法

(滑动窗口 + 单调队列) $O(n)$

首先，看到连续子数组/子区间的问题，很容易就想到用滑动窗口来做，即维护l, r指针，指针内部形成满足题目要求的区间。

这题重点在于如何维护区间的最大值最小值。回忆经典的滑动窗口最大值问题，我们可以用两个单调队列分别维护这段区间的最大值和最小值，于是问题便迎刃而解。

每次移动r指针，同时维护单调队列。判断区间是否满足要求（即最大值 - 最小值 <= limit)，不满足则移动l指针并维护两个单调队列直到满足要求。

时间复杂度

只需要遍历一遍数组，l, r指针均为单方向移动，复杂度为O(N).

Python 代码

from collections import deque
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        up = deque() # 单调上升队列，头为区间最小值
        down = deque() # 单调下降队列，头为区间最大值
        l = 0
        res = 0
        for r in range(len(nums)):
            while len(up) > 0 and nums[up[-1]] >= nums[r]: # 维护上升队列
                up.pop()
            # 注意队列里放的必须是下标而不是值，这样才能在移动左指针的时候更新队列
            up.append(r) 
            while len(down) > 0 and nums[down[-1]] <= nums[r]: # 维护下降队列
                down.pop()
            down.append(r)
            # 当发现条件不满足（即最大值-最小值>limit)时移动左指针
            while l < r and nums[down[0]] - nums[up[0]] > limit: 
                if l == down[0]:
                    down.popleft()
                if l == up[0]:
                    up.popleft()
                l += 1
            res = max(res, r - l + 1) # 更新结果
        return res