Implement FreqStack, 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 to
FreqStack.push(int x)will be such that0 <= x <= 10^9. - It is guaranteed that
FreqStack.pop()won’t be called if the stack has zero elements. - The total number of
FreqStack.pushcalls will not exceed10000in a single test case. - The total number of
FreqStack.popcalls will not exceed10000in a single test case. - The total number of
FreqStack.pushandFreqStack.popcalls will not exceed150000across all test cases.
这道题让我们实现一种最大频率栈，有入栈和出栈功能，需要每次出栈的都是栈中出现频率最大的数字，若有多个数字的频率相同，那么离栈顶最近的元素先出栈。刚开始看到这道题的时候，博主立马联想到了 LRU Cache 和 LFU 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)
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
