#include<bits/stdc++.h>
using namespace std;
const int mysize = 5e4 + 1;
int d[mysize];
int max_win[mysize] = {}, min_win[mysize] = {};
int calculate_max_length(int d[], int n, int k, int &l, int &r) {
int max_front = 1, max_tail = 0;
int min_front = 1, min_tail = 0;
int ans = -1;
for (int i = 1; i <= n; i++) {
while (max_front <= max_tail && d[i] > d[max_win[max_tail]]) {
max_tail--;
}
max_win[++max_tail] = i;
while (min_front <= min_tail && d[i] < d[min_win[min_tail]]) {
min_tail--;
}
min_win[++min_tail] = i;
while (d[max_win[max_front]] - d[min_win[min_front]] > k) {
if (max_win[max_front] > min_win[min_front]) {
min_front++;
} else {
max_front++;
}
}
if (ans < i - max(max_win[max_front - 1] + 1, min_win[min_front - 1] + 1) + 1) {
ans = i - max(max_win[max_front - 1] + 1, min_win[min_front - 1] + 1) + 1;
l = max(max_win[max_front - 1] + 1, min_win[min_front - 1] + 1);
r = i;
}
}
return ans;
}
int main() {
int n, k;
int ans1 = -1, ans2 = -1;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
sort(d + 1, d + n + 1);
int l1 = 0, r1 = 0;
ans1 = calculate_max_length(d, n, k, l1, r1);
for (int i = l1; i <= r1; i++) {
d[i] = d[r1 + (i - l1 + 1)];
}
n -= (r1 - l1 + 1);
fill(max_win, max_win + n + 1, 0);
fill(min_win, min_win + n + 1, 0);
int l2 = 0, r2 = 0;
ans2 = calculate_max_length(d, n, k, l2, r2);
cout << ans1 + ans2;
return 0;
}
用滑动窗口做的,两个单调队列分别维护子区间的最大值最小值。排列完一个陈列架之后(找到了第一个最长子区间之后)在原数组中把已经被选择的钻石删去,然后再找一次最长子区间.两个长度相加就是答案