最大频率栈

最大频率栈

实现以下接口：

class FreqStack {
public:
    // 在栈中加入一个元素 val
    void push(int val);
    // 从栈中删除并返回出现频率最高的元素
    // 如果频率最高的元素不止一个，
    // 则返回最近添加的那个元素
    int pop();
}

分析: 仔细思考一下 push 和 pop 方法，难点如下：

1、每次 pop 时，必须要知道频率最高的元素是什么。

2、如果频率最高的元素有多个，还得知道哪个是最近 push 进来的元素。

为了实现上述难点，我们要做到以下几点：

1、肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。

2、我们得知道一个频率 freq 对应的元素有哪些，且这些元素要有时间顺序。

3、随着 pop 的调用，每个 val 对应的频率会变化，所以还得维持一个映射记录每个 val 对应的 freq

代码如下：

#include <map>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

class FreqStack {
 private:
  int maxFreq;                      // 当前最大freq
  map<int, int> keyToFreq;          // 元素对应的freq
  map<int, stack<int>> freqToKeys;  // 同一freq的元素在同一个stack

 public:
  FreqStack() { maxFreq = 0; }
  void push(int key);
  int pop();
};

void FreqStack::push(int key) {
  // 更新keyToFreq
  auto freq = keyToFreq[key] + 1;
  keyToFreq[key] = freq;
  // 跟新maxFreq
  maxFreq = max(freq, maxFreq);
  // 插入元素
  freqToKeys[freq].push(key);
}

int FreqStack::pop() {
  if (maxFreq == 0) return -1;
  // 弹出最大freq栈栈顶元素
  auto k = freqToKeys[maxFreq].top();
  freqToKeys[maxFreq].pop();
  // 更新该元素对应的freq
  keyToFreq[k] -= 1;
  // 更新maxFreq
  if (freqToKeys[maxFreq].empty()) maxFreq--;
  return k;
}