本文时间知识点
C++队列、双向队列
C++算法：滑动窗口及双指针总结
LeetCode1438. 绝对差不超过限制的最长连续子数组
给你一个整数数组 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 <= 105
1 <= nums[i] <= 109
0 <= limit <= 109
滑动窗口（错误解法)
i从小到大枚举nums[i]，令nums[i1…i]是符合条件的子数组。
由于abs(i1-1,nums[i])>limit，故nums[i1-1…i1+1]一定不符合条件，故从i1可以判断。
如果nums[i1]和nums[i+1]符合条件，则i1++。
错误原因：nums[i1+2]可以和nums[i]不符合
滑动窗口+有序映射（集合)
记录nums[i1…i]的值和下标。如果set最小的值和nums[i]超过限制，则将下标小于等于最小值下标的删除。set最大值超限，也是如此。处理完超限后，将nums[i]放到set。此时的set.size就是以 nusm[i]结尾的最长子数组长度。
时间复杂度：O(nlogn)
滑动窗口+单调队列
两个双向队列分别记录(nums[i],i) ，其中i ∈ \in ∈[0,j-1]。
minQue如果有元素x，其下标为i1 ，符合小于x <nums[i]- limit，则删除下标小于等于i1的元素。
i1 <i2，且nums[i1]>= nums[i2] 。如果i1符合条件，则i2也一定符合。而i2符合会删除i1。故i1可以省略，或者说i1被i2淘汰后。
淘汰后，从队首到队尾，严格升序，即最小元素在队首。
maxQue类似，严格降序。
队首可能有多个元素超限，一个队列超限后，要清理另一个队列的下标。
时间复杂度：O(n)
代码
核心代码
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
deque<int> minQue, maxQue;
int ans = 0;
int del = -1;
for (int i = 0; i < nums.size(); i++) {
while (minQue.size() && (nums[minQue.front()] < nums[i] - limit )) {
del = max(del, minQue.front());
minQue.pop_front();
}
while (maxQue.size() && (nums[maxQue.front()] > nums[i] + limit)) {
del = max(del, maxQue.front());
maxQue.pop_front();
}
while (minQue.size() && (minQue.front() <= del)) { minQue.pop_front(); }
while (maxQue.size() && (maxQue.front() <= del)) { maxQue.pop_front(); }
while (minQue.size() && (nums[minQue.back()] >= nums[i])) {
minQue.pop_back();
}
while (maxQue.size() && (nums[maxQue.back()] <= nums[i])) {
maxQue.pop_back();
}
minQue.emplace_back(i);
maxQue.emplace_back(i);
ans = max(ans, i - del);
}
return ans;
}
};
单元测试
vector<int> nums;
int limit;
TEST_METHOD(TestMethod1)
{
nums = {1,5 }, limit = 3;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(1, res);
}
TEST_METHOD(TestMethod2)
{
nums = { 1,5 }, limit = 5;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(2, res);
}
TEST_METHOD(TestMethod11)
{
nums = { 8, 2, 4, 7 }, limit = 4;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(2, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 10,1,2,4,7,2 }, limit = 5;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(4, res);
}
TEST_METHOD(TestMethod13)
{
nums = { 4,2,2,2,4,4,2,2 }, limit = 0;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(3, res);
}
TEST_METHOD(TestMethod14)
{
nums = { 2,2,2,4,4,2,5,5,5,5,5,2 }, limit = 2;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(6, res);
}
TEST_METHOD(TestMethod15)
{
nums = { 24,12,71,33,5,87,10,11,3,58,2,97,97,36,32,35,15,80,24,45,38,9,22,21,33,68,22,85,35,83,92,38,59,90,42,64,61,15,4,40,50,44,54,25,34,14,33,94,66,27,78,56,3,29,3,51,19,5,93,21,58,91,65,87,55,70,29,81,89,67,58,29,68,84,4,51,87,74,42,85,81,55,8,95,39 }, limit = 87;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(25, res);
}
TEST_METHOD(TestMethod16)
{
nums = { 7,40,10,10,40,39,96,21,54,73,33,17,2,72,5,76,28,73,59,22,100,91,80,66,5,49,26,45,13,27,74,87,56,76,25,64,14,86,50,38,65,64,3,42,79,52,37,3,21,26,42,73,18,44,55,28,35,87 }, limit = 63;
auto res = Solution().longestSubarray(nums, limit);
AssertEx(9, res);
}
