-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path895.maximum-frequency-stack.py
More file actions
134 lines (113 loc) · 3.83 KB
/
895.maximum-frequency-stack.py
File metadata and controls
134 lines (113 loc) · 3.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
# Tag: Hash Table, Stack, Design, Ordered Set
# Time: O(1)
# Space: O(N)
# Ref: -
# Note: -
# Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.
# Implement the FreqStack class:
#
# FreqStack() constructs an empty frequency stack.
# void push(int val) pushes an integer val onto the top of the stack.
# int pop() removes and returns the most frequent element in the stack.
#
# If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
#
#
#
#
# Example 1:
#
# Input
# ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
# [[], [5], [7], [5], [7], [4], [5], [], [], [], []]
# Output
# [null, null, null, null, null, null, null, 5, 7, 5, 4]
#
# Explanation
# FreqStack freqStack = new FreqStack();
# freqStack.push(5); // The stack is [5]
# freqStack.push(7); // The stack is [5,7]
# freqStack.push(5); // The stack is [5,7,5]
# freqStack.push(7); // The stack is [5,7,5,7]
# freqStack.push(4); // The stack is [5,7,5,7,4]
# freqStack.push(5); // The stack is [5,7,5,7,4,5]
# freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
# freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
# freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
# freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
#
#
# Constraints:
#
# 0 <= val <= 109
# At most 2 * 104 calls will be made to push and pop.
# It is guaranteed that there will be at least one element in the stack before calling pop.
#
#
from collections import defaultdict
class FreqStack:
def __init__(self):
self.frequency = defaultdict(int)
self.table = defaultdict(list)
self.max_freq = 0
def push(self, val: int) -> None:
self.frequency[val] += 1
freq = self.frequency[val]
self.max_freq = max(self.max_freq, freq)
self.table[freq].append(val)
def pop(self) -> int:
val = self.table[self.max_freq].pop()
self.frequency[val] -= 1
if len(self.table[self.max_freq]) == 0:
self.max_freq -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
class FreqStack:
def __init__(self):
self.frequency = {}
self.table = []
def push(self, val: int) -> None:
if val not in self.frequency:
self.frequency[val] = 0
self.frequency[val] += 1
freq = self.frequency[val]
if freq > len(self.table):
self.table.append([val])
else:
self.table[freq - 1].append(val)
def pop(self) -> int:
last = self.table[-1]
val = last.pop()
if len(last) == 0:
self.table.pop()
self.frequency[val] -= 1
if self.frequency[val] == 0:
del self.frequency[val]
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
from collections import defaultdict
import heapq
class FreqStack:
def __init__(self):
self.heap = []
self.frequency = defaultdict(int)
self.pos = 0
def push(self, val: int) -> None:
self.frequency[val] += 1
self.pos += 1
heapq.heappush(self.heap, (-self.frequency[val], -self.pos, val))
def pop(self) -> int:
cur = heapq.heappop(self.heap)
val = cur[2]
self.frequency[val] -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()