> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/stack/895-maximum-frequency-stack.md).

# 895     Maximum Frequency Stack

## 895. [Maximum Frequency Stack](https://leetcode.com/problems/maximum-frequency-stack/description/)

## 1. Question

Implement`FreqStack`, a class which simulates the operation of a stack-like data structure.

`FreqStack` has two functions:

* `push(int x)`, which pushes an integer`x`onto 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 to`FreqStack.push(int x)`will be such that`0 <= x <= 10^9`.
* It is guaranteed that`FreqStack.pop()`won't be called if the stack has zero elements.
* The total number of`FreqStack.push`calls will not exceed`10000`in a single test case.
* The total number of`FreqStack.pop`calls will not exceed`10000`in a single test case.
* The total number of`FreqStack.push`and`FreqStack.pop`calls will not exceed`150000`across all test cases.

## 2. Implementation

**(1) HashTable + Stack**

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

```java
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)