[LeetCode][895. Maximum Frequency Stack] HashMap Solution with Detailed Explanation
By Long Luo
This article is the solution HashMap Solution with Detailed Explanation of Problem 895. Maximum Frequency Stack.
Intuition
Let’s look at the problem description first.
- \(\texttt{FreqStack()}\) constructs an empty frequency stack.
- void \(\texttt{push(int val)}\) pushes an integer val onto the top of the stack.
- int \(\texttt{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.
The requirements of the problems can be listed in 3 rules:
- Pop the stack by the max frequency;
- Among all the elements with the same (maximum) frequency, pop the element closest to the stack’s top.
To simplify the problem, let’s just ignore rule 2 for now, it looks easier.
Step 1
We care more about the frequency of the elements. We can use \(\texttt{HashMap}\) to record the frequency of each element.
Additionally, we also care about max Frequency, the current maximum frequency of any element in the stack. we use the \(\textit{maxFreq}\) to store the maximum frequency.
The code is as follows.