895. Maximum Frequency Stack

https://leetcode.com/problems/maximum-frequency-stack/

solution

import collections

class FreqStack:
    def __init__(self):
        self.freq_counter = collections.defaultdict(int)
        self.freq_key = collections.defaultdict(list)
        self.max_freq = 0

    def push(self, val: int) -> None:
        self.freq_counter[val] += 1
        self.max_freq = max(self.max_freq, self.freq_counter[val])
        self.freq_key[self.freq_counter[val]].append(val)

    def pop(self) -> int:
        val = self.freq_key[self.max_freq].pop()
        self.freq_counter[val] -= 1
        if not self.freq_key[self.max_freq]:
            self.max_freq -= 1
        return val

时间复杂度：O(1) 空间复杂度：O()