# 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.