仅供自己学习

 

也是一种滑动窗口的思想，而左指针右移的条件是子串最大值与最小值之差 > limit时就将left相加。而主要的时间消耗是寻找字串的最大值和最小值，需要一个合适的数据结构。这里用的一个multiset，基于红黑树的平衡搜索二叉树，是可以存放重复的元素的从小到大排列的序列。主要的方法就是，每次加入一次nums的元素，就用最后一个即最大元素减去第一个即最小元素，差大于limit就删除left所指的在multiset的元素，并且left右移。

 1 class Solution {
 2 public:
 3     int longestSubarray(vector<int>& nums, int limit) {
 4         int left=0,right=0;
 5         multiset<int> q;
 6         int size=nums.size();
 7         int maxlen=INT_MIN;
 8         while(right<size){
 9             q.insert(nums[right]);
10             while(*q.rbegin()-*q.begin()>limit){
11                 q.erase(q.find(nums[left++]));
12             }
13             maxlen=max(maxlen,right-left+1);
14             right++;
15         }
16         return maxlen;
17     }
18 };

 

还有一种方法就是使用双端队列，用两个，一个用来存储最大元素，一个用来存储最小元素。

 1 class Solution {
 2 public:
 3     int longestSubarray(vector<int>& nums, int limit) {
 4        deque<int> MAX_DEQUE,MIN_DEQUE;
 5        int right=0,left=0,size=nums.size();
 6        int maxlen=INT_MIN;
 7        while(right<size){
 8            while(!MAX_DEQUE.empty()&&nums[right]>MAX_DEQUE.back())
 9                 MAX_DEQUE.pop_back();
10             while(!MIN_DEQUE.empty()&&nums[right]<MIN_DEQUE.back())
11                 MIN_DEQUE.pop_back();
12             MAX_DEQUE.push_back(nums[right]);
13             MIN_DEQUE.push_back(nums[right]);
14             if(MAX_DEQUE.front()-MIN_DEQUE.front()>limit){
15                 if(MAX_DEQUE.front()==nums[left])
16                     MAX_DEQUE.pop_front();
17                 if(MIN_DEQUE.front()==nums[left])
18                     MIN_DEQUE.pop_front();
19                 left++;
20             }
21             maxlen=max(maxlen,right-left+1);
22             right++;
23        }
24        return maxlen;
25     }
26 };

 

8~11的目的是如果队列非空并且新元素比最后一个更大或最小，那么就会移除MIN和MAX的最后一个元素，并且会在12-13行两个队列都加入新元素。

最开始第一个元素都会被加入两个队列，第二次则会去除MIN或MAX队列的最后一个元素，并且两个队列在加入新元素。在两个队列都加入新元素的原因是因为每个元素在不同字串可能是最大或最小的，如果不是最大或最小就会在8-11行去掉。如果差大于limit后就需要清除在队列中并且left所指的元素。