题目

解题思路

两个哈希表,一个变量

cnt记录每个元素出现的频率

result记录每个频率的栈

max_Count 或者 MAX用来记录当前最大频率

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class FreqStack:
    def __init__(self):
        self.cnt = defaultdict(int)
        self.result = defaultdict(list)
        self.MAX = 0

    def push(self, val: int) -> None:
        cnt = self.cnt
        stack = self.result
        cnt[val] += 1
        if cnt[val] > self.MAX:
            self.MAX = cnt[val]
        stack[cnt[val]].append(val)

    def pop(self) -> int:
        cnt, stack = self.cnt, self.result
        MAX = self.MAX
        ans = stack[MAX].pop()
        if not stack[MAX]:
            stack.pop(MAX)
            self.MAX -= 1
        cnt[ans] -= 1
        return ans

C++

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
26
27
28
29
30
31
32
33
34
class FreqStack {
public:
    FreqStack() {
        max_count = 0;
    }
    
    void push(int val) {
        // 频率增加
        ++cnt[val];
        // 更新最大频率
        if (cnt[val] > max_count) {
            max_count = cnt[val];
        }
        // 频率对应的栈更新
        result[cnt[val]].push(val);

    }
    
    int pop() {
        int ans = result[max_count].top();
        result[max_count].pop();
        // 栈为空时更新最大频率
        if (result[max_count].empty()) {
            --max_count;
        }
        --cnt[ans];
        return ans;

    }
private:
    unordered_map<int, int> cnt;
    unordered_map<int, stack<int>> result;
    int max_count;
};