Method 1
class FreqStack:
#TC: O(log n!)
#SC: O(1)
#Just use heap to recoder the freqeucy and the lasteness of appearance
def __init__(self):
self.heap = []
self.freq = {}
self.index = 0
def push(self, val: int) -> None:
if val in self.freq:
self.freq[val] += 1
else:
self.freq[val] = 1
self.index += 1
heapq.heappush(self.heap, (-self.freq[val], -self.index, val))
def pop(self) -> int:
val = self.heap[0][-1]
self.freq[val] -= 1
heapq.heappop(self.heap)
return val
Method 2
class FreqStack:
#TC: O(1)
#SC: O(ele)
def __init__(self):
self.maxfreq = 0 #record maximum freq
self.freqStack = collections.defaultdict(list) #record the appearance of val at different freq
self.freqVal = {} #record freq of each val
def push(self, val: int) -> None:
self.freqVal[val] = self.freqVal.get(val, 0) + 1
self.maxfreq = max(self.maxfreq, self.freqVal[val])
self.freqStack[self.freqVal[val]].append(val)
def pop(self) -> int:
val = self.freqStack[self.maxfreq][-1]
self.freqStack[self.maxfreq].pop()
self.freqVal[val] -= 1
if len(self.freqStack[self.maxfreq]) == 0:
self.maxfreq -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()