LeetCode-895. 最大频率栈【栈，哈希表，设计，有序集合】

题目描述：

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类:

FreqStack() 构造一个空的堆栈。
void push(int val) 将一个整数 val 压入栈顶。
int pop() 删除并返回堆栈中出现频率最高的元素。
如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

示例 1：

输入：
[“FreqStack”,“push”,“push”,“push”,“push”,“push”,“push”,“pop”,“pop”,“pop”,“pop”],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。

提示：

0 <= val <= 109
push 和 pop 的操作数不大于 2 * 104。
输入保证在调用 pop 之前堆栈中至少有一个元素。
https://leetcode.cn/problems/maximum-frequency-stack/

解题思路一：哈希表和栈。这道题奇妙之处在于把出现频率相同的值存储为一组元素，这样在pop的时候，找到频率最高的那组元素，按照后入先出的顺序，弹出即可。

还是以题目给的数据为例：

freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]//group为{1，{5,7}}
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]//group为{1，{5,7}} {2，{5,7}}
freqStack.push (4);//堆栈是 [5,7,5,7,4]//group为{1，{5,7,4}} {2，{5,7}}
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]//group为{1，{5,7,4}} {2，{5,7}} {3，{5}}}
然后最大频率为3，那么pop就会从freq 为3的那组值中选择最后加入的值弹出, 当前应该弹出值5{1，{5,7,4}} {2，{5,7}} {3，{ }}}。
1
2
3
4
5
6
7

从group最后的状态可以看出{1，{5,7,4}} {2，{5,7}} {3，{5}}}。
只要依次由maxFreq的栈中出栈元素即可。
即从右往左数，5,7,5,4即是出栈顺序。

class FreqStack {
public:
    int maxFreq;//遍历group用
    unordered_map<int,int> freq;//值和对应的频率，更新group用
    unordered_map<int,stack<int>> group;//需要注意的是group只是增加和遍历，没有覆盖和删除操作。
    FreqStack() {maxFreq=0;}//初始化   
    void push(int val) {
        ++freq[val];
        maxFreq=max(maxFreq,freq[val]);
        group[freq[val]].push(val);//val的频率增加了1，也就是说频率为freq_map[val]的值加一，对应更新group。
    }    
    int pop() {
        int x=group[maxFreq].top();group[maxFreq].pop();//获取栈顶元素和出栈
        --freq[x];//pop和push操作有可能是交替进行的，所以维护更新。
        if(group[maxFreq].empty()) --maxFreq;
        return x;        
    }
};
/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：O(1)对于 push 和 pop操作，时间复杂度为 O(1)。
空间复杂度：O(n)//n为FreqStack中的元素个数。

解题思路二：无注释版。

class FreqStack {
public:
    int maxFreq;
    unordered_map<int,int> freq;
    unordered_map<int,stack<int>> group;
    FreqStack() {maxFreq=0;}    
    void push(int val) {
        ++freq[val];
        maxFreq=max(maxFreq,freq[val]);
        group[freq[val]].push(val);
    }    
    int pop() {
        int x=group[maxFreq].top();group[maxFreq].pop();
        --freq[x];
        if(group[maxFreq].empty()) --maxFreq;
        return x;        
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度：O(1)对于 push 和 pop操作，时间复杂度为 O(1)。
空间复杂度：O(n)//n为FreqStack中的元素个数。

解题思路三：优化！这里我们直接省去维护最大值的操作以数组下标代替。

class FreqStack {
    unordered_map<int, int> cnt;
    vector<stack<int>> stacks;
public:
    void push(int val) {
        if (cnt[val] == stacks.size()) // 这个元素的频率已经是目前最多的，现在又出现了一次
            stacks.push_back({}); // 那么必须创建一个新栈
        stacks[cnt[val]].push(val);
        ++cnt[val]; // 更新频率
    }

    int pop() {
        int val = stacks.back().top(); // 弹出最右侧栈的栈顶
        stacks.back().pop();
        if (stacks.back().empty()) // 栈为空
            stacks.pop_back(); // 删除
        --cnt[val]; // 更新频率
        return val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(1)对于 push 和 pop操作，时间复杂度为 O(1)。
空间复杂度：O(n)//n为FreqStack中的元素个数。