[数据结构与算法]Leetcode——最大频率栈

1. 题目

2. 题解

• 维持两个Map + 一个变量记录当前最大频率
• 一个Map存储：当前元素——元素频率
• 一个Map存储：频率——频率对应元素（用栈存储）

class FreqStack {
    Map<Integer, Integer> freq;             //元素——频率
    Map<Integer, Deque<Integer>> group;     //频率——具有该频率的元素的映射
    int maxfreq;

    public FreqStack() {
        freq = new HashMap();
        group = new HashMap();
        maxfreq = 0;
    }

    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;    //计算当前x的频率
        freq.put(x, f);                         
        if(f > maxfreq)                         //判断当前元素频率是否为最大频率
            maxfreq = f;

        group.computeIfAbsent(f, k -> new LinkedList()).push(x);     //存储当前频率——当前频率对应的元素（放入栈中），以满足如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素
    }
    

    
    public int pop() {
        int x = group.get(maxfreq).pop();       //弹出当前最大频率所对应的元素，若存在多个，弹出接近栈顶；
        freq.put(x, freq.get(x) - 1);           //弹出元素的频率减1
        if(group.get(maxfreq).size() == 0)      //如果当前最大频率只有一个元素，将更新最大频率元素
            maxfreq--;                          //频率为maxfreq的元素减少了一个，剩余值中最大频率为 maxfreq - 1
        return x;
    }
}

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