# 895. Maximum Frequency Stack

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.

这道题让我们实现一种最大频率栈，有入栈和出栈功能，需要每次出栈的都是栈中出现频率最大的数字，若有多个数字的频率相同，那么离栈顶最近的元素先出栈。刚开始看到这道题的时候，博主立马联想到了 LRU CacheLFU Cache，想着会不会也需要在迭代器上做文章，但实际是我想多了，虽然同为 Hard 的题目，这道题的解法却要比之前那两道要简单的多。这里只跟数字出现的频率有关，只有在频率相等的情况下才会考虑栈的后入先出的特性，所以一定是需要统计栈中每个数字出现的频率的，我们使用一个 HashMap 来建立每个数字跟其出现次数之间的映射。由于频率相等的数字可能有多个，所以我们必须知道某个特性频率下都有哪些数字，再用一个 HashMap 来建立频率和该频率下所有的数字之间的映射，可以将这些数组放到一个数组或者一个栈中，这里为了简便起见，就使用一个数组了。另外，我们还需要维护一个当前最大频率的变量，可以通过这个值到 HashMap 中快速定位数组的位置。好，一切准备就绪之后就开始解题吧，对于入栈函数 push()，首先需要将x对应的映射值加1，并更新最大频率 mxFreq，然后就是要把x加入当前频率对应的数组中，注意若某个数字出现了3次，那么数字会分别加入频率为 1，2，3 的映射数组中。接下来看出栈函数 pop() 如何实现，由于我们知道当前最大频率 mxFreq，就可以直接去 HashMap 中取出该频率下的所有数字的数组，题目说了若频率相等，取离栈顶最近的元素，这里就是数组末尾的数组，取到之后，要将该数字从数组末尾移除。移除之后，我们要检测一下，若数组此时为空了，说明当前最大频率下之后一个数字，取出之后，最大频率就要自减1，还有不要忘记的就是取出数字的自身的频率值也要自减1，参见代码如下：
解法一：

class FreqStack {
public:

``````FreqStack() {}

void push(int x) {
mxFreq = max(mxFreq, ++freq[x]);
m[freq[x]].push_back(x);
}

int pop() {
int x = m[mxFreq].back();
m[mxFreq].pop_back();
if (m[freq[x]--].empty()) --mxFreq;
return x;
}
``````

private:

``````int mxFreq;
unordered_map<int, int> freq;
unordered_map<int, vector<int>> m;
``````

};

我们还可以使用 multimap 来建立频率和数字之间的映射，利用其可重复的特性，那么同一个频率就可以映射多个数字了。同时，由于 multimap 默认是按从小到大排序的，而我们希望按频率从大到小排序，所以加上一个参数使其改变排序方式。在入栈函数中，将x的频率自增1，然后跟x组成 pair 对儿加入 multimap 中。在出栈函数中，由于其是按从大到小排序的，而且后进的排在前面，那么第一个映射对儿就是频率最大且最后加入的数字，将其取出并从 multimap 中移除，并同时将该数字的映射频率值减1即可，参见代码如下：
解法二：

class FreqStack {
public:

``````FreqStack() {}

void push(int x) {
m.insert({++freq[x], x});
}

int pop() {
int x = m.begin()->second;
m.erase(m.begin());
--freq[x];
return x;
}
``````

private:

``````unordered_map<int, int> freq;
multimap<int, int, greater_equal<int>> m;
``````

};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/895

https://leetcode.com/problems/maximum-frequency-stack/

https://leetcode.com/problems/maximum-frequency-stack/discuss/163410/C%2B%2BJavaPython-O(1)

https://leetcode.com/problems/maximum-frequency-stack/discuss/229638/C%2B%2B-multimap-solution-132-ms

https://leetcode.com/problems/maximum-frequency-stack/discuss/163453/JAVA-O(1)-solution-easy-understand-using-bucket-sort

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation