力扣 1438. 绝对差不超过限制的最长连续子数组 单调队列+思维

https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

思路：很容易想到，枚举区间的起始点$l$，然后找到第一个不满足题意的终结点$r$，显然$[l,r?1]$是满足题意的，那么可以更新答案$ans=max(ans,r?l)$。那么整体框架就有了，初始令$l=0$，移动$r$直到$[l,r]$不满足题意，更新答案，然后移动$l$直到$[l,r]$满足题意，循环下去。怎么判断这个区间是否满足题意呢？遍历求最大最小值？$O(n^2)$显然不行。观察$l、r$移动的过程，不难想到维护两个单调队列，即可$O(1)$取得区间最大最小值。

class Solution {
    
public:int longestSubarray(vector<int>& nums, int limit) {
    deque<int> Max,min;int siz=nums.size(),i=0,j=0,ans=0,r=0;while(j<siz){
    while(j<siz){
    while(!Max.empty()&&nums[j]>=nums[Max.back()])Max.pop_back();while(!min.empty()&&nums[j]<=nums[min.back()])min.pop_back();Max.push_back(j);min.push_back(j);if(nums[Max.front()]-nums[min.front()]>limit)break;++j;}//[i,j)是合法的ans=max(ans,j-i);while(i<siz&&nums[Max.front()]-nums[min.front()]>limit){
    if(i==Max.front())Max.pop_front();if(i==min.front())min.pop_front();++i;}//[i,j]是合法的++j;}return ans;}
};