> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md).
# 1438. 绝对差不超过限制的最长连续子数组
### 题目地址(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
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
```
### 前置知识
* 有序集合
* 二分法
* 滑动窗口
* 单调栈
### 公司
* 暂无
### 二分法
这道题核心的就是求连续子数组的最大值和最小值，而由于数据是静态的，因此没必要使用线段树。
这里我们可以手动维护一个有序数组 d。其中的数据表示的就是**某一个连续子数组**，只不过 d 是已经排好序的。比如原有的子数组是：\[3,1,2]，那么 d 就是 \[1,2,3]。我们可以使用二分法在 $logn$ 的时间找到插入点，并在最坏 $O(n)$ 的时间完成插入和删除。因此最坏时间复杂度是 $o(n^2)$。
接下来，我们使用滑动窗口技巧，代码上可使用双指针。而由于 d 的长度就是窗口的大小，因此使用一个指针表示右端点即可，因为左端点可通过 **右端点 - d 的长度 + 1**得出。
#### 思路
#### 关键点
* 维护一个有序数组，并通过二分法找到插入位置
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def longestSubarray(self, A: List[int], limit: int) -> int:
d = []
ans = 1
for i, a in enumerate(A):
bisect.insort(d, a)
if len(d) > 1:
while d[-1] - d[0] > limit:
d.remove(A[i - len(d)+1])
ans = max(ans, len(d))
return ans
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n^2)$
* 空间复杂度：$O(n)$
### 有序集合
#### 思路
和上面思路类似。 只不过将数据结构从数组变成了平衡树，这样插入和删除的复杂度可以降低到 $O(logn)$。Python 的 SortedList 可以达到此目的。Java 可用 TreeMap，C++ 可用 multiset 代替。
代码基本也是类似的，大家自己看下即可。
#### 关键点
* 平衡二叉树优化插入和删除的时间复杂度
#### 代码
* 语言支持：Python3
Python3 Code:
```python
from sortedcontainers import SortedList
class Solution:
def longestSubarray(self, A: List[int], limit: int) -> int:
d = SortedList()
ans = 1
for i, a in enumerate(A):
d.add(a)
if len(d) > 1:
while d[-1] - d[0] > limit:
d.remove(A[i - len(d)+1])
ans = max(ans, len(d))
return ans
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(n)$
### 单调队列
#### 思路
单调队列可快速得到最大值和最小值。因此我们可以使用两个队列，分别计算区间的最大值和最小值，接下来的思路和上面类似。即维护一个滑动窗口即可。
关于单调队列/栈可参考我之前写的文章 [单调栈解题模板秒杀八道题](https://lucifer.ren/blog/2020/11/03/monotone-stack/)
我们需要使用两个单调队列，一个单调增另外一个单调减。因此两个队列会存储窗口内所有的数(会有重叠)，而一个单调队列显然无法做到。
比如 nums = \[8,2,4,7], limit = 4，那么刚开始：
* 单调递增队列就是 q1：\[8]
* 单调递减队列就是 q2：\[8]
接下来：
* 单调递增队列就是 q1：\[8]
* 单调递减队列就是 q2：\[8,2]，这个时候大于 limit，需要移除 q1，q1 变为 \[]
> 注意此时无需管 q2 内部差大于 limit
接下来：
* 单调递增队列就是 q1：\[4]
* 单调递减队列就是 q2：\[8,4]
接下来：
* 单调递增队列就是 q1：\[4,7]
* 单调递减队列就是 q2：\[8,7]
end
之所以我们不使用单调栈是因为我们需要移除左侧的数组， 因此需要在两端进行操作，这正是队列的基本操作。
#### 关键点
* 单调队列获取最大最小值
#### 代码
* 语言支持：Python3
Python3 Code:
q1 是单调递减的队列，q2 是单调递增的队列。因此 q1\[0] 是最大值，q2\[0] 是最小值。
```python
class Solution:
def longestSubarray(self, A: List[int], limit: int) -> int:
q1, q2 = collections.deque(), collections.deque()
ans = 1
i = 0
for j, a in enumerate(A):
while q1 and q1[-1] < a:
q1.pop()
q1.append(a)
while q2 and q2[-1] > a:
q2.pop()
q2.append(a)
while i < j and q1 and q2 and q1[0] - q2[0] > limit:
if A[i] == q1[0]: q1.popleft()
elif A[i] == q2[0]: q2.popleft()
i += 1
ans = max(ans, j - i + 1)
return ans
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
