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

题目描述

数组是整数数组，需要找最长的连续子数组长度。要求是子数组内的最大值-最小值<=limit

基本分析

1. 求最长连续子数组长度考虑什么框架？双指针
2. 怎么维护区间内的最大值和最小值？定义两个单调队列，分别维护最大值和最小值
3. 双指针怎么移动？r每次向右移动一个，这个时候判断r的值是不是必要的；然后判断区间是不是满足要求，不满足的时候维护队列的头部，并且移动l直到满足要求。

代码

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        l, r = 0, 0
        # 递增，递减
        minq, maxq = deque(), deque()
        ans = 0

        n = len(nums)
        while r < n:
            while minq and minq[-1] > nums[r]:
                minq.pop()
            while maxq and maxq[-1] < nums[r]:
                maxq.pop()
            minq.append(nums[r])
            maxq.append(nums[r])
            # 处理头
            while minq and maxq and maxq[0] - minq[0] > limit:
                if nums[l] == minq[0]:
                    minq.popleft()
                if nums[l] == maxq[0]:
                    maxq.popleft()
                l += 1
            
            ans = max(ans, r - l  + 1)
            r += 1
        
        return ans

总结

1. 双指针需要有序性，这里可以满足。
2. 双指针怎么促进了队列的更新？尾部进来元素后，需要更新队尾，看以前元素是不是必要；区间不满足要求后，需要移动到满足要求为止，当每移动一次l，就需要判断队头和nums[l]的关系，看是不是要弹出。
3. 这里单调队列里面放的是值，不是索引