Q895 最大频率栈

题目描述

实现 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需要满足的两个API

class FreqStack {

    // 在栈中加入一个元素 val
    public void push(int val) {}

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

由此我们知道，我们需要快速查询到频率最高的元素，如果有多个频率最高的元素，还需要得到离栈顶最近的元素

那么，我们仔细思考一下 push 和 pop 方法，难点如下：

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

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

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

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

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

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

综上，我们可以先实现 FreqStack 所需的数据结构：

public class FreqStack {
    Map<Integer, Integer> valueToFreq = new HashMap<>();
    Map<Integer, Stack<Integer>> freqToValue = new HashMap<>();
    int maxFreq = 0;
}

push(int val)方法

现在我们来思考如何实现push()方法。

1、首先需要查询val是否存在

如果存在：将val的freq+1;

如果不存在：在valToFreq 中添加 val的Freq为1.

2、在val的freq对应的Stack中添加val

3、判断val的freq是否大于maxFreq

如果大于，maxFreq =freq;

如果不大于；维持现状

public void push(int val) {
        if (valueToFreq.containsKey(val)) {
            valueToFreq.put(val, valueToFreq.get(val) + 1);
        } else {
            valueToFreq.put(val, 1);
        }
        int freq = valueToFreq.get(val);
        freqToValue.putIfAbsent(freq,new Stack<>());
        freqToValue.get(freq).add(val);
        if(freq>maxFreq){
            maxFreq=freq;
        }
    }

pop()方法

1、将maxFreq对应的Stack中的栈顶元素弹出

2、将弹出元素val对应的freq-1;

3、如果stack为空，则maxFreq-1;

public int pop() {
    Stack<Integer> stack = freqToValue.get(maxFreq);
    int val =stack.pop();
    valueToFreq.put(val,maxFreq-1);
    if(stack.isEmpty()){
        maxFreq--;
    }
    return val;
}

代码实现

public class FreqStack {
    Map<Integer, Integer> valueToFreq = new HashMap<>();
    Map<Integer, Stack<Integer>> freqToValue = new HashMap<>();
    int maxFreq = 0;

    public FreqStack() {
        
    }

    public void push(int val) {
        if (valueToFreq.containsKey(val)) {
            valueToFreq.put(val, valueToFreq.get(val) + 1);
        } else {
            valueToFreq.put(val, 1);
        }
        int freq = valueToFreq.get(val);
        freqToValue.putIfAbsent(freq,new Stack<>());
        freqToValue.get(freq).add(val);
        if(freq>maxFreq){
            maxFreq=freq;
        }
    }
    
    public int pop() {
        Stack<Integer> stack = freqToValue.get(maxFreq);
        int val =stack.pop();
        valueToFreq.put(val,maxFreq-1);
        if(stack.isEmpty()){
            maxFreq--;
        }
        return val;
    }
}

Q895 最大频率栈