传送门：
题意：
给长度为 n 的序列 和 限制值 k，求最长的子区间，子区间满足区间中任意两个数的差的绝对值不大于k
思路：
双单调队列，一个维护当前区间最大，一个维护当前区间最小，如果当前区间最大-最小满足条件，呢么当前区间整体满足条件，否则让单调队列中的除去当前存在的左端点即可
参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
int ans;
int q1[100005], q2[100005], a[100005];
void solv(int n, int k)
{
int head1 = 0, tail1 = -1, head2 = 0, tail2 = -1, res = 0, l = 0;
for (int i = 0; i < n; i++)
{
while (head1 <= tail1 && a[q1[tail1]] >=a[i])
tail1--;
while (head2 <= tail2 && a[q2[tail2]] <=a[i])
tail2--;
while (head1 <= tail1 && q1[head1] < l)
head1++;
while (head2 <= tail2 && q2[head2] < l)
head2++;
q1[++tail1] = i;
q2[++tail2] = i;
if (a[q2[head2]] - a[q1[head1]] <= k)
res = max(res, i - l + 1);
else
l++;
}
ans=res;
}
public:
int longestSubarray(vector<int>& nums, int limit) {
int n=nums.size();
for(int i=0;i<n;i++)
a[i]=nums[i];
solv(n,limit);
return ans;
}
};
|
