leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1838.cpp (1187B)

0 static const auto _ = [] { 1 cin.tie(0); 2 ios::sync_with_stdio(0); 3 return 0; 4 }(); 5 class Solution { 6 public: 7 int maxFrequency(vector<int> &nums, int k) const { 8 static long long prefix[100001]; 9 const int n = nums.size(); 10 11 memset(prefix, 0x00, sizeof(prefix)); 12 for (int i = 0; i < n; i++) 13 prefix[nums[i]]++; 14 15 for (int i = 0, j = 0; i <= 100000; i++) { 16 while (prefix[i] > 0) { 17 nums[j++] = i, prefix[i]--; 18 } 19 } 20 21 prefix[0] = 0; 22 for (int i = 1; i < n; i++) 23 prefix[i] = nums[i - 1] + prefix[i - 1]; 24 25 int res = 0; 26 for (int crnt = 0; crnt < n; crnt++) { 27 int low = 0, high = crnt - 1; 28 while (low <= high) { 29 const int mid = low + (high - low) / 2; 30 const long long left = crnt - mid; 31 const long long sum = prefix[crnt] - prefix[mid]; 32 if (left * nums[crnt] - sum <= k) 33 high = mid - 1; 34 else 35 low = mid + 1; 36 } 37 res = max(res, crnt - high); 38 } 39 40 return res; 41 } 42 };