力扣1438.绝对差不超过限制的最长连续子数组
力扣1438.绝对差不超过限制的最长连续子数组
难点:保存数组缩小后的最大最小值
- 用两个单调队列分别处理最大值和最小值
class Solution { public: int longestSubarray(vector<int>& nums, int limit) { deque<int> quemax,quemin; int n = nums.size(),res=0; for(int i=0,j=0;i<n;i++) { while(!quemax.empty() && quemax.back() < nums[i]) quemax.pop_back(); while(!quemin.empty() && quemin.back() > nums[i]) quemin.pop_back(); quemax.push_back(nums[i]); quemin.push_back(nums[i]); while(!quemax.empty() && !quemin.empty() && quemax.front() - quemin.front() > limit) { if(quemax.front() == nums[j]) quemax.pop_front(); if(quemin.front() == nums[j]) quemin.pop_front(); j ++; } res = max(res,i-j+1); } return res; } };