原题地址（中等）

方法1—暴力（时间超限）

思路

首先想到的就是暴力，双重循环来尝试所有的可能。不过时间超限了。

代码

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
         int n = nums.size(), ans = 0;
         if(!n)     return 0;
         for(int i = 0; i < n; i++) {
             int maxVal = nums[i], minVal = nums[i];
             for(int j = i; j < n; j++) {
                 if(nums[j] > maxVal)   maxVal = nums[j];
                 if(nums[j] < minVal)   minVal = nums[j];
                 if(maxVal - minVal <= limit)   ans = max(ans, j - i + 1);
             }
         }
         return ans;
    }
};

时空复杂度

方法2—滑动窗口+有序集合

这道题其实是考察了对语言各种模板函数的运用程度。
c++的话用multiset或者map就很好做了。

思路

这个是看的官解，主要是利用了c++自带的红黑树。然后使用滑动窗口枚举每一个位置作为右端点，找到其对应的最靠左的左端点，满足区间中最大值与最小值的差不超过limit。

也可以用 map<int, int> ,map会对数据自动排序，内部也是红黑树。

代码

multiset

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> ms;
        int n = nums.size(), left = 0, right = 0, ans = 0;
        while(right < n) {
            ms.insert(nums[right]);
            while(*ms.rbegin() - *ms.begin() > limit)
                ms.erase(ms.find(nums[left++]));
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

map

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        map<int, int> m;
        int n = nums.size(), left = 0, right = 0, ans = 0;
        while(right < n) {
            m[nums[right]]++;
            while(m.rbegin()->first - m.begin()->first > limit){
                m[nums[left++]]--;
                if(m[nums[left-1]] == 0)  m.erase(nums[left-1]);
            }
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

时空复杂度

时间 空间

方法3—滑动窗口+队列

思路

可用两个双端队列来存储最大最小值，不断更新，这样寻找子串的最大最小值直接取两个队列的头元素相减即可。
见官解方法2

代码

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> queMax, queMin;
        int n = nums.size(), left = 0, right = 0, ans = 0;
        while(right < n) {
            // 保证queMax的元素都比nums[right]大
            while(!queMax.empty() && queMax.back() < nums[right])
                queMax.pop_back();
            // 保证queMin的元素都比nums[right]小
            while(!queMin.empty() && queMin.back() > nums[right])
                queMin.pop_back();
            queMax.push_back(nums[right]);
            queMin.push_back(nums[right]);
            while(!queMax.empty() && !queMin.empty() && queMax.front() - queMin.front() > limit) {
                if(nums[left] == queMax.front()) queMax.pop_front();
                if(nums[left] == queMin.front()) queMin.pop_front();
                left++;
            }
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

时空复杂度

均为