题解 | 相差不超过k的最多数

#include <iostream>
#include <map>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	map<int, int> counting;
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		counting[tmp]++; 
	}
	int* a = new int[n];
	//前缀和 
	int* sum = new int[n];
	sum[0] = 0;
	int cnt = 1;
	for (map<int, int>::iterator it = counting.begin(); it != counting.end(); it++) {
		a[cnt] = it -> first;
		sum[cnt] = it -> second + sum[cnt - 1];
		cnt++; 
	}
	sum[cnt] = sum[cnt - 1];
	int left = 1, right = 1, final_ans = 0, ans = 0;
	//推荐使用left < cnt判定，逻辑较为清楚不容易出错 
	while (right < cnt) {
		while ((right < cnt - 1 && a[right + 1] - a[left] <= k) || right == cnt - 1) {
			right++;
		}
		ans = max(ans, sum[right] - sum[left - 1]);
		left++;
	}
	cout << ans << endl;
}