# LeetCode - 895. Maximum Frequency Stack
###### tags: `LeetCode` `Guide` `C++` `Hard`
> 原題連結: https://leetcode.com/problems/maximum-frequency-stack/

> Difficulty: <span style="color: red;">Hard</span>

## 題目說明
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.

## 說明

這題的目標是要實作一個類別，其中有兩個函式需完成:
1. **push()** -> push一個int到整個stack的頂端
2. **pop()** -> pop出(並刪除)一個**出現次數最多的數中最靠近頂端**的值

## Code與解析
### 作法. Stack by Hash <span style="font-size:5px; color:green;">[Accept]</span>
> Runtime: 264 ms > faster than 29.98%
> Memory: 68.2 MB > less than 100.00%

class FreqStack {
    map<int, int> frq; // Frequency of a number
    map<int, vector<int>> lvl; // Record the number that its freq higher than the freq (int).
    int top; // Top of stack, used with lvl.
public:
    FreqStack() {
        frq.clear();
        lvl.clear();
        top = -1;
    }
    
    void push(int x) {
        frq[x]++; // Frquency of a number
        if(frq[x] > top) top = frq[x]; // If freq of a number is highest, update it.
        lvl[frq[x]].push_back(x); // Push the number into the corresponding freq.
    }
    
    int pop() {
        int rtn = lvl[top].back(); // Record the number that should be return.
        lvl[top].pop_back(); // Pop the number.
        frq[rtn]--; // Decrease the freq of the number.
        if(lvl[top].empty()) top--; // If no more number with the freq, decrease the top freq to find most-freq number.
        return rtn;
    }
};

這題的重點在於以下幾點:
1. 要記錄次數
2. 如何找到最靠近末端而最頻繁出現的值

那根據這些考量，我們利用

map<int, int> frq;
第一個int為數字，第二個int為該數字出現的次數

來記錄次數，而實際上的stack部分，則要巧妙的運用到

map<int, vector<int>> lvl;
int為次數，vector<int>為大於此次數的數字

拿Example1舉個例子，在經過前面的**push**之後，理論上stack會是:

> [5, 7, 5, 7, 4, 5]

然而，依據我們儲存的方式，實際上會長成這個樣子:

>> frq:
>> [4] -> 1
>> [5] -> 3
>> [7] -> 2
>
>> lvl: top = 3
>> [1] -> {5, 7, 4}
>> [2] -> {5, 7}
>> [3] -> {5}

這樣有什麼好處呢?我們接著看。如果現在執行了**pop()**，此時從lvl中來看，最高次數的最末端是5，所以5會被pop掉，那儲存的樣子就會變成:

>> frq:
>> [4] -> 1
>> [5] -> 2
>> [7] -> 2
>
>> lvl: top = 2
>> [1] -> {5, 7, 4}
>> [2] -> {5, 7}

一次可能還不明顯，我們再pop一次，這次從lvl中可以發現，最高次數2的那個vector中，存著兩個數，那因為7比較後面，表示7是比較晚被push進來的，所以次數最高且最靠近末端的就會是7，得到以下:

>> frq:
>> [4] -> 1
>> [5] -> 2
>> [7] -> 1
>
>> lvl: top = 2
>> [1] -> {5, 7, 4}
>> [2] -> {5}

依此類推。如此一來就能把這題給搞定了！