Leetcode - 895 maximum frequency stack (Design - hash table + priority queue hash table + stack)*

Hashtable + Priority queue

class FreqStack {
    
    class Node{
    
        // Value size 
        int val;
        // Frequency of occurrence of value 
        int freq;
        // The time when the value appears   The greater the time, the closer to the top of the stack 
        int t;
        public Node(int val,int freq,int t){
    
            this.val = val;
            this.freq = freq;
            this.t = t;
        }
    }
    class NodeComparator implements Comparator<Node> {
    
          // If the occurrence frequency is different, sort in reverse order by frequency 
         public int compare(Node n1, Node n2) {
    
             if(n2.freq != n1.freq)
              return n2.freq - n1.freq;
             else// If the frequency of occurrence is the same, sort in reverse order according to the entry time 
              return n2.t - n1.t;
         }
    }
    private Map<Integer,Integer> map;// Record the frequency of each value 
    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(); */

Double hash table + Stack

class FreqStack {
    
    // Record the frequency of each value 
    private Map<Integer,Integer> freqMap;
    // Record each frequency   Corresponding value   Value is put in the stack 
    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  Add one to the corresponding frequency 
        freqMap.put(val,freqMap.getOrDefault(val,0) + 1);
        int f = freqMap.get(val);
        // If val The corresponding frequency has exceeded the maximum frequency 
        if(f > maxFreq)
           maxFreq = f;// Update maximum frequency 
        if(freqStack.get(f) == null)// Push 
           freqStack.put(f,new LinkedList<>());
        freqStack.get(f).offerFirst(val);
        
    }
    
    public int pop(){
    
        // From the stack corresponding to the maximum frequency   Pop up the top of the stack 
        int val = freqStack.get(maxFreq).pollFirst();
        // The frequency corresponding to this value is minus one 
        freqMap.put(val,freqMap.getOrDefault(val,0) - 1);
        // If the stack corresponding to the maximum frequency is empty 
        if(freqStack.get(maxFreq).size() == 0)
        {
    
            //freqStack Remove the maximum frequency 
            freqStack.remove(maxFreq);
            // Reduce the maximum frequency by one 
            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(); */