数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中长度最长的连续子数组，其绝对差小于或等于限制
假设我们有一个名为 nums 的整数数组和一个整数 limit，我们需要找到最长非空子数组的大小，使得该子数组中任意两个元素的绝对差小于或等于给定的 limit。
因此，如果输入类似于 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。
为了解决这个问题，我们将遵循以下步骤：
ret := 0，i := 0，j := 0
定义一个双端队列 maxD 和另一个双端队列 minD
n := nums 的大小
初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
当 (maxD 不为空且 maxD 的最后一个元素 < nums[i]) 时，执行：
从 maxD 中删除最后一个元素
当 (minD 不为空且 minD 的最后一个元素 > nums[i]) 时，执行：
从 minD 中删除最后一个元素
将 nums[i] 插入到 maxD 的末尾
将 nums[i] 插入到 minD 的末尾
当 (maxD 的第一个元素 - minD 的第一个元素) > k 时，执行：
如果 nums[j] 与 maxD 的第一个元素相同，则：
从 maxD 中删除第一个元素
如果 nums[j] 与 minD 的第一个元素相同，则：
从 minD 中删除第一个元素
(j 加 1)
ret := ret 和 (i - j + 1) 的最大值
返回 ret
示例
让我们看看以下实现以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestSubarray(vector<int>& nums, int k) {
int ret = 0;
int i = 0;
int j = 0;
deque<int> maxD;
deque<int> minD;
int n = nums.size();
for (int i = 0; i < n; i++) {
while (!maxD.empty() && maxD.back() < nums[i])
maxD.pop_back();
while (!minD.empty() && minD.back() > nums[i])
minD.pop_back();
maxD.push_back(nums[i]);
minD.push_back(nums[i]);
while (maxD.front() - minD.front() > k) {
if (nums[j] == maxD.front())
maxD.pop_front();
if (nums[j] == minD.front())
minD.pop_front();
j++;
}
ret = max(ret, i - j + 1);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {7,8,2,4};
cout << (ob.longestSubarray(v, 4));
}输入
{7,8,2,4}, 4输出
2
447 次浏览
