滑动窗口 + 双端队列
给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组,则返回 0 。
示例 1:
输入:nums = [8,2,4,7], limit = 4
输出:2
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
deque<int> mx, mn;
int j = 0, ans = 0;
for(int i = 0; i < n; i ++){
while(!mx.empty() && nums[mx.back()] <= nums[i]) mx.pop_back();
mx.push_back(i);
while(!mn.empty() && nums[mn.back()] >= nums[i]) mn.pop_back();
mn.push_back(i);
while(nums[mx.front()] - nums[mn.front()] > limit){
j ++;
if(mn.front() < j) mn.pop_front();
if(mx.front() < j) mx.pop_front();
}
ans = max(ans, i - j + 1);
}
return ans;
}
};