2856.cpp (1194B)
1 class Solution { 2 public: 3 int minLengthAfterRemovals(const vector<int> &nums) const { 4 priority_queue<int> pq; 5 6 int count = 1; 7 for (int i = 1; i < nums.size(); i++) { 8 if (nums[i] != nums[i - 1]) { 9 pq.push(count); 10 count = 1; 11 } else 12 count++; 13 } 14 pq.push(count); 15 16 while (pq.size() > 1) { 17 const int first = pq.top(); 18 pq.pop(); 19 const int second = pq.top(); 20 pq.pop(); 21 if (first > 1) pq.push(first - 1); 22 if (second > 1) pq.push(second - 1); 23 } 24 25 return pq.size() ? pq.top() : 0; 26 } 27 }; 28 29 // Not sure why this works... 30 class Solution { 31 public: 32 int minLengthAfterRemovals(const vector<int> &nums) const { 33 const int n = nums.size(); 34 int count = 1, maxi = 0; 35 for (int i = 1; i < n; i++) { 36 if (nums[i] != nums[i - 1]) { 37 maxi = max(maxi, count); 38 count = 1; 39 } else 40 count++; 41 } 42 maxi = max(maxi, count); 43 44 if (maxi <= n / 2) return n % 2; 45 return 2 * maxi - n; 46 } 47 };