消除相同球的最大数量 - Python 代码实现

首先我们可以用一个哈希表记录每种球的出现次数，然后从左到右遍历球，维护当前连续相同球的数量cnt，如果当前球不同于前一个球，则尝试将前面所有相同的球全部消除。具体来说，如果哈希表中当前球的出现次数大于cnt，则将前面的所有相同球全部消除，并将cnt重置为哈希表中当前球的出现次数。最后将所有剩余的球数量相加即为答案。时间复杂度为O(n)。以下是代码实现：

n = int(input())
a = list(map(int, input().split()))

cnt = 0
ans = 0
freq = {}
for i in range(n):
    if a[i] not in freq:
        freq[a[i]] = 0
    freq[a[i]] += 1
    if a[i] != a[i-1]:
        while freq[a[i-1]] > cnt:
            freq[a[i-1]] -= cnt
            ans += cnt
            cnt = freq[a[i-1]]
        ans += cnt
        cnt = freq[a[i]]
while freq[a[n-1]] > cnt:
    freq[a[n-1]] -= cnt
    ans += cnt
    cnt = freq[a[n-1]]
ans += cnt

print(ans)