1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

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

1. Use brute force:

//TLE
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        if(nums.size()<=1) return nums.size();  
        int maxlen = 1;
        int len = 1;
        int submax = 0, submin = 0;
        for(int i = 0; i < nums.size(); i++){
            submax = nums[i];
            submin = nums[i];
            len = 1;
            for(int j = i + 1; j < nums.size(); j++){
                submax = max(submax, nums[j]);
                submin = min(submin, nums[j]);
                if(abs(submax-nums[j])<=limit && abs(submin-nums[j])<=limit){
                    len++;
                    maxlen = max(maxlen, len);
                }
                else
                    break;
            }
        }
        return max(maxlen, 1);
    }
};

2. Use sliding window:

https://www.bilibili.com/video/BV1Cf4y1m7aN

//204 ms    51.3 MB
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> max_q;
        deque<int> min_q;
        int result = 0;
        int l = 0;
        for(int r = 0; r < nums.size(); r++){
            while(!min_q.empty() && nums[r] < min_q.back())
                min_q.pop_back();
            while(!max_q.empty() && nums[r] > max_q.back())
                max_q.pop_back();
            min_q.push_back(nums[r]);
            max_q.push_back(nums[r]);
            while(max_q.front() - min_q.front() > limit){
                if(max_q.front() == nums[l]) //remove itself
                    max_q.pop_front();
                if(min_q.front() == nums[l]) //remove itself
                    min_q.pop_front();
                l++;
            }
            result = max(result, r - l + 1);
        }
        return result;
    }
};