力扣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;
        }
    };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22