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 xonto 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 150000across 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

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation