leetcode895最大频率栈

原题链接:
https://leetcode.cn/problems/maximum-frequency-stack/description/

解法1: 双哈希

/**
    双哈希 
    一个hash记录值 及其 对应的出现次数
    另一个hash 记录 次数出现相同的数 的集合 
    max 记录当前出现的最大频率 即根据题意需要返回的数
 */

class FreqStack {
    // 出现次数 以及 对应的数
    HashMap<Integer,List<Integer>> map = new HashMap<>();
    // 记录每个数出现的次数
    HashMap<Integer,Integer> cnts = new HashMap<>();
    int max;

    public FreqStack() {
        map = new HashMap<>();
        cnts = new HashMap<>();
        max = 0;
    }
    
    public void push(int val) {
        int freq = cnts.getOrDefault(val,0);
        freq++;
        // 更新出现的次数
        cnts.put(val,freq);
        // 得到出现 相对应的数的集合
        var arr = map.getOrDefault(freq,new ArrayList<>());
        arr.add(val);
        // 更新map
        map.put(freq,arr);
        // 更新最大出现频率
        max = Math.max(max,freq);
    }
    
    public int pop() {
        // 得到当前最大元素 对应出现的数
        var arr = map.get(max); 
        // 移除 最新加入 最大出现频率集合的数
        int ans = arr.remove(arr.size() - 1);
        // 更新该数出现的次数
        cnts.put(ans,cnts.get(ans) - 1);
        // 如果当前最大频率对应的出现的数集合 长度为0 更新最大长度
        if(arr.size() == 0){
            max--;
        }
        return ans;
    }
}

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