895 maximum frequency stack

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

这就是你心心念念的stack of stack题，这道题跟max stack有点像的原因是都需要按push顺序pop掉某些满足条件的值，所以只是存个frequency在某个node里显然不可行了。

那么是否可以像max stack那样用treemap+list解决呢？其实也可以，我们treemap里是freq->stack of nodes，我们pop掉某个freq对应stack里的node，freq-1对应的stack里也有这个node。但是注意到treemap找到max val的时间是O(logn)，如果我们一直维护maxfreq的话就可以在O(1)时间找到，也就没有了用tree map的意义。那为什么我们在max stack里不这么做呢？因为一旦max freq对应的node被pop完了，我们能立马知道上一个maxFreq是max freq-1，但是如果max val对应的node被pop完了，我们并不能立马知道上一个max val是多少。

class FreqStack {
    // freq -> stack
    Map<Integer, Deque<Integer>> stacks= new HashMap<>();
    // value -> freq
    Map<Integer, Integer> freqs = new HashMap<>();
    int maxFreq = 0;
    
    public FreqStack() {}
    
    public void push(int val) {
        int freq = freqs.getOrDefault(val, 0);
        freqs.put(val, freq+1);
        maxFreq = Math.max(freq+1, maxFreq);
        Deque<Integer> stack = stacks.get(freq+1);
        if (stack == null) {
            stack = new ArrayDeque<>();
            stacks.put(freq+1, stack);
        }
        //这里其实很妙，在[1,freq+1]范围内对应的每一个stack都恰好存了一个这个val
        //在pop掉这个val时，它的frequency发生了变化，但我们不需要把它从某个stack转移到另一个stack
        //因为上一个freq对应的stack里也恰好存了一个val
        stack.push(val);
    }
    
    public int pop() {
        Deque<Integer> stack = stacks.get(maxFreq);
        int ans = stack.pop();
        freqs.put(ans, maxFreq-1);
        if (stack.isEmpty()) {
            // 你也许会想不对呀不应该想办法知道上一个maxFreq是多少吗，怎么直接减一，
            // 万一没有val的频率是maxFreq-1怎么办?
            // 你可能忽略了这是frequency，aka count，所以一个数如果有maxFreq个，pop掉一个一定还剩maxFreq-1个
            // 如果有maxFreq的val没有了，最多就是maxFreq-1了，对应的val和stack一定存在
            maxFreq--;
        }
        return ans;
    }
}

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

很喜欢的一道题！但是感觉会初见杀吧