# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/stack/895-maximum-frequency-stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.