【C++单调队列】1438. 绝对差不超过限制的最长连续子数组|1672

本文时间知识点

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 <= 10⁵
1 <= nums[i] <= 10⁹
0 <= limit <= 10⁹

滑动窗口（错误解法)

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);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功