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

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

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

示例 1：

输入：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 。
示例 2：

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

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

这道题可以用滑动窗口来解决。

保存滑动窗口中的最大值和最小值，这个可以使用两个队列来解决，一个递增一个递减，队列中一定包含最右端元素。

from typing import *
from collections import deque, defaultdict


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        que1 = deque([])  # 包括最后一个元素的递增
        que2 = deque([])  # 包括最后一个元素的递减
        j = 0
        max_len = 1
        for i in range(len(nums)):
            while que1 and nums[i] > que1[-1]:
                que1.pop()
            while que2 and nums[i] < que2[-1]:
                que2.pop()
            que1.append(nums[i])
            que2.append(nums[i])
            while que1 and que2 and abs(que2[0] - que1[0]) > limit:
                if nums[j] == que1[0]:
                    que1.popleft()
                if nums[j] == que2[0]:
                    que2.popleft()
                j+=1
            max_len = max(max_len, i - j + 1)
        return max_len

用队列毕竟不好想，实在不行用集合计数，算法慢了一点。

from typing import *
from collections import deque,defaultdict
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        dic={}
        j=0
        max_len=1
        for i in range(len(nums)):
            if nums[i] not in dic:
                dic[nums[i]]=1
            else:
                dic[nums[i]]+=1
            while j<=i and abs(max(dic.keys())-min(dic.keys()))>limit:
                dic[nums[j]]-=1
                if dic[nums[j]]==0:
                    del dic[nums[j]]
                j+=1
            max_len=max(max_len,i-j+1)
        return max_len