题目描述

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

• push(int x)，将整数 x 推入栈中。
• pop()，它移除并返回栈中出现最频繁的元素。
  • 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

样例

输入：
["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]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

注意

• 对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
• 如果栈的元素数目为零，则保证不会调用 FreqStack.pop()。
• 单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。
• 单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。
• 所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

算法

(堆，哈希表) $O(n \log n)$

1. 建立一个哈希表，用来记录每个数字出现的次数。
2. 建立一个大根堆，每个元素是个三元组 出现次数，插入时间，数字。如果出现次数相同，则插入时间大的优先。
3. 设置时间戳记录插入时间。
4. 每次插入时，首先将该数字出现次数加 1，时间戳累加 1，构造三元组放入堆中。栈中重复的数字会按照这样的方式在堆中排好序。
5. 每次弹出时，从堆顶弹出元素，将该数字出现次数减 1 即可。

时间复杂度

• 每次插入元素需要修改哈希表，并且在堆中插入元素；每次弹出同理；故时间复杂度为 $O(n \log n)$。

C++ 代码

class FreqStack {
public:
    priority_queue<pair<int, pair<int, int>>> heap;
    map<int, int> counter;
    int stamp;
    FreqStack() {
        heap = priority_queue<pair<int, pair<int, int>>>();
        counter = map<int, int>();
        stamp = 0;
    }

    void push(int x) {
        counter[x]++;
        stamp++;
        heap.push(make_pair(counter[x], make_pair(stamp, x)));
    }

    int pop() {
        int ans = heap.top().second.second;
        heap.pop();
        counter[ans]--;
        return ans;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 */