Description
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 with push(val) and pop() methods.
Examples
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:
Pop returns most frequent element
Input:
["FreqStack","push","push","push","push","pop","push","pop","pop","pop"], [[],[1],[2],[1],[3],[],[1],[],[],[]]Output:
[null,null,null,null,null,1,null,1,3,2]Explanation:
FreqStack is created. Push 1,2,1,3. Pop returns 1 (frequency 2). Push 1 again. Pop returns 1 (frequency 2, most recent). Pop returns 3 (frequency 1, most recent). Pop returns 2 (frequency 1, remaining).
Input:
["FreqStack","push","push","push","push","push","pop","pop","push","pop"], [[],[8],[8],[9],[8],[9],[],[],[10],[]]Output:
[null,null,null,null,null,null,8,9,null,8]Explanation:
FreqStack is created. Push 8,8,9,8,9. Pop returns 8 (frequency 3). Pop returns 9 (frequency 2, most recent). Push 10. Pop returns 8 (frequency 2, most recent among highest frequency).
Constraints
- •
0 ≤ val ≤ 10^9 - •
At most 2 * 10^4 calls to push and pop