LeetCode 895 - Maximum Frequency Stack

https://leetcode.com/problems/maximum-frequency-stack/

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

• Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
• It is guaranteed that FreqStack.pop() won't be called if the stack has zero elements.
• The total number of FreqStack.push calls will not exceed 10000 in a single test case.
• The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
• The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases

https://leetcode.com/problems/maximum-frequency-stack/discuss/163410/C%2B%2BJavaPython-O(1)

Hash map freq will count the frequence of elements.
Hash map m is a map of stack.
If element x has n frequence, we will push x n times in m[1], m[2] .. m[n]
maxfreq records the maximum frequence.

push(x) will push x tom[++freq[x]]
pop() will pop from the m[maxfreq]

Approach 1: Stack of Stacks

Evidently, we care about the frequency of an element. Let freq be a Map from $x$ to the number of occurrences of $x$.

Also, we (probably) care about maxfreq, the current maximum frequency of any element in the stack. This is clear because we must pop the element with the maximum frequency.

The main question then becomes: among elements with the same (maximum) frequency, how do we know which element is most recent? We can use a stack to query this information: the top of the stack is the most recent.

To this end, let group be a map from frequency to a stack of elements with that frequency. We now have all the required components to implement FreqStack.

Algorithm

Actually, as an implementation level detail, if x has frequency f, then we'll have x in all group[i] (i <= f), not just the top. This is because each group[i] will store information related to the ith copy of x.

Afterwards, our goal is just to maintain freq, group, and maxfreq as described above.

  Map<Integer, Integer> freq;

  Map<Integer, Stack<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;

    freq.put(x, f);

    if (f > maxfreq)

      maxfreq = f;

    group.computeIfAbsent(f, z -> new Stack()).push(x);

  }

  public int pop() {

    int x = group.get(maxfreq).pop();

    freq.put(x, freq.get(x) - 1);

    if (group.get(maxfreq).size() == 0)

      maxfreq--;

    return x;

  }

X. https://leetcode.com/problems/maximum-frequency-stack/discuss/163453/JAVA-O(1)-solution-easy-understand-using-bucket-sort
https://leetcode.com/problems/maximum-frequency-stack/discuss/163438/Java-O(1)-solution-using-list-of-stacks-with-detailed-explanation
https://zxi.mytechroad.com/blog/desgin/leetcode-895-maximum-frequency-stack/

We have n  stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x)  # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

https://github.com/cherryljr/LeetCode/blob/master/Maximum%20Frequency%20Stack.java

class FreqStack {

    List<Stack<Integer>> bucket;
    HashMap<Integer, Integer> map;
    
    public FreqStack() {
        bucket = new ArrayList<>();
        map = new HashMap<>();
    }
    
    public void push(int x) {
        map.put(x, map.getOrDefault(x, 0) + 1);
        int freq = map.get(x);
        if (freq - 1 >= bucket.size()) {
            bucket.add(new Stack<Integer>());
        }
        bucket.get(freq - 1).add(x);
    }
    
    public int pop() {
        int freq = bucket.size();
        int x = bucket.get(freq - 1).pop();
        if (bucket.get(freq - 1).isEmpty()) bucket.remove(bucket.size() - 1);
        
        map.put(x, map.get(x) - 1);
        if (map.get(x) == 0) map.remove(x);
        
        return x;
    }
}

X. PriorityQueue
https://blog.csdn.net/fuxuemingzhu/article/details/82752010
同时优化两个目标：出现的频率和出现的索引。所以天然想到用优先级队列。python的优先级队列是个最小堆，而我们要优化的目标是求最大，因此，使用负号即可。

使用m保存出现的次数，使用index保存索引，使用q表示堆。

把出现的次数和出现的索引取反进堆，这样每次弹出堆的时候都是把这两个目标优化了的。pop的时候要更新频率。

我考虑了以下问题：

我觉得是否有个问题？因为pop的过程中并没有更正已经进堆的那些数字的频率，也就是堆里面仍然是以前的频率。这里是否有问题？
1
其实，事实上这么想是错的，我们堆里面保留的并不是每个数字真实的频率，而是它入堆的时候的频率。当每次Pop的时候会把各个字符出现的频率恢复到它入堆前的样子（题目给出了如果同样的频率时，弹出最后push进去的数字）。当这个数字是最大频率数字，并且多次出现的时候，尽可能弹出靠最后的进入数字保证了提前进入堆的那些数字的频率是正确的。

这是个巧妙的解法，而且第一眼看上去好像是错的。非常有意思
https://leetcode.com/problems/maximum-frequency-stack/discuss/163416/Java-Priority-Queue-easy-understand

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

class FreqStack {
    
    class Pair{
        int num;
        int count;
        int time;
        
        Pair(int num, int count, int time){
            this.num = num;
            this.count = count;
            this.time = time;
        }
        
    }
    
    private PriorityQueue<Pair> queue;
    private HashMap<Integer,Integer> map;
    private int clock = 0;
    public FreqStack() {
        queue = new PriorityQueue<Pair>((a,b) -> (a.count == b.count?b.time-a.time:b.count-a.count));
        map = new HashMap();
    }
    
    public void push(int x) {
        Pair pair = new Pair(x,map.getOrDefault(x,0)+1,clock++);
        map.put(x,map.getOrDefault(x,0)+1);
        queue.offer(pair);
    }
    
    public int pop() {
        Pair cur = queue.poll();
        // update
        map.put(cur.num,map.getOrDefault(cur.num,0)-1);
        return cur.num;
    }   
}