Popularity Pile
Hard · stack
A pile of numbers starts empty and receives a list of operations. operations[i] is either "push" or "pop", and args[i] holds its arguments: [x] for a "push" and [] (empty) for a "pop".
"push"puts one more copy ofxon the pile."pop"removes one copy of the most popular value in the pile and returns that value. The most popular value is the one with the most copies currently in the pile. If several values share the highest number of copies, pick the one whose most recently pushed copy is newest. The copy that is removed is that newest copy of the chosen value.
A "pop" is never given when the pile is empty. Return a list with the value returned by every "pop", in the order they appear.
Examples
Example 1
Input: operations = ["push", "push", "push", "push", "pop", "pop", "pop", "pop"], args = [[5], [7], [5], [7], [], [], [], []]
Output: [7, 5, 7, 5]
5 and 7 tie with two copies each and the newest copy is a 7, so 7 goes first. Then 5 leads with two copies to one. Last, 5 and 7 tie at one copy each and the 7 is newer.
Example 2
Input: operations = ["push", "push", "push", "pop", "pop", "pop"], args = [[4], [9], [4], [], [], []]
Output: [4, 9, 4]
4 has two copies, so it goes first. After that 4 and 9 tie with one copy each, and the remaining 4 was pushed first, so 9 goes before it.
Example 3
Input: operations = ["push", "push", "push", "pop", "push", "pop", "pop"], args = [[2], [3], [2], [], [3], [], []]
Output: [2, 3, 3]
After the first pop the pile holds one 2 and one 3, then another 3 is pushed. Two copies of 3 beat one of 2, and afterwards the tie at one copy each goes to 3 as the newer.
Constraints
- 1 <= len(operations) <= 10^4
- len(args) == len(operations)
- operations[i] is push or pop
- 0 <= x <= 10^9
- A pop is only given when the pile holds at least one value