LeetCode - 895 最大频率栈(设计- 哈希表+优先队列 哈希表 + 栈） *

哈希表+优先队列

class FreqStack {
    
    class Node{
    
        //值的大小
        int val;
        //值出现的频率
        int freq;
        //值出现的时间 时间越大越靠近栈顶
        int t;
        public Node(int val,int freq,int t){
    
            this.val = val;
            this.freq = freq;
            this.t = t;
        }
    }
    class NodeComparator implements Comparator<Node> {
    
          //如果出现频率不一样按频率逆序排序
         public int compare(Node n1, Node n2) {
    
             if(n2.freq != n1.freq)
              return n2.freq - n1.freq;
             else//如果出现频率一样按进入时间逆序排序
              return n2.t - n1.t;
         }
    }
    private Map<Integer,Integer> map;//记录每个值出现的频率
    private PriorityQueue<Node> queue;
    private int t;
    public FreqStack() {
    
       map = new HashMap<>();
       queue = new PriorityQueue<>(new NodeComparator());
       t = 0;
    }
    
    public void push(int val) {
    
         map.put(val,map.getOrDefault(val,0) + 1);
         queue.offer(new Node(val,map.getOrDefault(val,0),t++));
    }
    
    public int pop() {
    
       int val = queue.poll().val;
       map.put(val,map.getOrDefault(val,0) - 1);
       if(map.getOrDefault(val,0) == 0)
         map.remove(val);
       return val;
    }
}

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

双哈希表 + 栈

class FreqStack {
    
    //记录每个值出现的频率
    private Map<Integer,Integer> freqMap;
    //记录每个频率 对应的值 值放在栈里面
    private Map<Integer,Deque<Integer>> freqStack;
    private int maxFreq;
    public FreqStack() {
    
        freqMap = new HashMap<>();
        freqStack = new HashMap<>();
        maxFreq = 0;
    }
    
    public void push(int val) {
    
        //val 对应频率加一
        freqMap.put(val,freqMap.getOrDefault(val,0) + 1);
        int f = freqMap.get(val);
        //如果val对应的频率已经超过最大频率
        if(f > maxFreq)
           maxFreq = f;//更新最大频率
        if(freqStack.get(f) == null)//入栈
           freqStack.put(f,new LinkedList<>());
        freqStack.get(f).offerFirst(val);
        
    }
    
    public int pop(){
    
        //从最大频率对应的栈 弹出栈顶
        int val = freqStack.get(maxFreq).pollFirst();
        //该值对应的频率减一
        freqMap.put(val,freqMap.getOrDefault(val,0) - 1);
        //如果最大频率对应的栈空了
        if(freqStack.get(maxFreq).size() == 0)
        {
    
            //freqStack移除最大频率
            freqStack.remove(maxFreq);
            //将最大频率减一
            maxFreq -= 1;
        }
        return val;
    }
}

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