leetcode

0 // Binary search: O(n * logn)

1 class Solution {

2 public:

3 int maximumBeauty(vector<int> &nums, int k) const {

4 sort(begin(nums), end(nums));

5 int res = 1;

6

7 for (int i = 0; i < size(nums); i++) {

8 const auto it = upper_bound(begin(nums), end(nums), 2 * k + nums[i]);

9 res = max(res, (int)distance(begin(nums) + i, it));

10 }

11

12 return res;

13 }

14 };

15

16 // Line sweep: O(n)

17 class Solution {

18 public:

19 int maximumBeauty(const vector<int> &nums, int k) const {

20 int mini = INT_MAX, maxi = INT_MIN;

21 static int count[200002];

22

23 memset(count, 0x00, sizeof(count));

24 for (const int n : nums) {

25 const int a = max(n - k, 0);

26 const int b = n + k + 1;

27

28 count[a]++;

29 count[b]--;

30

31 mini = min(mini, a);

32 maxi = max(maxi, b);

33 }

34

35 int res = 1;

36 for (int i = mini, acc = 0; i <= maxi; i++) {

37 acc += count[i];

38 res = max(res, acc);

39 }

40

41 return res;

42 }

43 };