895 Maximum Frequency Stack

895. Maximum Frequency Stack

1. Question

ImplementFreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integerxonto the stack.

• pop(), which removes and returns the most frequent element in the stack.

  • If there is a tie for most frequent element, the element closest to the top of the stack 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:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

• Calls toFreqStack.push(int x)will be such that0 <= x <= 10^9.

• It is guaranteed thatFreqStack.pop()won't be called if the stack has zero elements.

• The total number ofFreqStack.pushcalls will not exceed10000in a single test case.

• The total number ofFreqStack.popcalls will not exceed10000in a single test case.

• The total number ofFreqStack.pushandFreqStack.popcalls will not exceed150000across all test cases.

2. Implementation

(1) HashTable + Stack

思路: 用一个hashTable记录每个数字的frequency，用另一个hashTable存储拥有该frequency的所有数，由于题目要求有多有两个数出现频数最高时，返回最接近stack的那个，所以第二个hashTable的key就是frequency，value是Stack. 最后我们定义一个maxFreq来记录当前最高频数

class FreqStack {
    Map<Integer, Integer> freq;
    Map<Integer, Stack<Integer>> freqToStack;
    int maxFreq;

    public FreqStack() {
        freq = new HashMap();
        freqToStack = new HashMap();
        maxFreq = 0;
    }

    public void push(int x) {
        int curFreq = freq.getOrDefault(x, 0) + 1;
        freq.put(x, curFreq);
        maxFreq = Math.max(maxFreq, curFreq);

        if (!freqToStack.containsKey(curFreq)) {
            freqToStack.put(curFreq, new Stack());
        }
        freqToStack.get(curFreq).push(x);
    }

    public int pop() {
        int num = freqToStack.get(maxFreq).pop();
        freq.put(num, maxFreq - 1);

        if (freqToStack.get(maxFreq).isEmpty()) {
            --maxFreq;
        }
        return num;
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 */

3. Time & Space Complexity

HashTable + Stack: 时间复杂度push(): O(1), pop(): O(1), 空间复杂度O(n)