滑动窗口+有序序列(multiset)
思路
以后需要维护一个区间的最大值和最小值就用multiset,时间复杂度为logn
见: https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/
代码
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int left=0,right=0,max_len=0,n=nums.size();
multiset<int> mst;
for(;right<n;right++)
{
mst.insert(nums[right]);
while(*mst.rbegin()-*mst.begin()>limit)
{
mst.erase(mst.find(nums[left]));
left++;
}
max_len=max(max_len,right-left+1);
}
return max_len;
}
};