1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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) {
        int freq = freqMap.getOrDefault(val, 0) + 1;
        freqMap.put(val, freq);
        freqStack.computeIfAbsent(freq, a -> new ArrayDeque<>()).push(val);
        maxFreq = Math.max(maxFreq, freq);
    }

    public int pop() {
        int ans = freqStack.get(maxFreq).pop();
        freqMap.put(ans, freqMap.get(ans) - 1);
        if (freqStack.get(maxFreq).isEmpty()) {
            maxFreq -= 1;
        }
        return ans;
    }
}

这道题的解法是真的很精妙. 怎么想也想不出来这种解法. 我们想知道maxFreq的num是谁, 如果有多个, 那还要得到最后达到的那个. 这让我们自然而然想到使用stack, 因为按照时间先后, 后达到的先出来. 假设所有num出现的频率有个bound, 且我们知道, 那么就用一个stack, 去存达到这个bound的num都有谁, 这样后达到的就能先出来. 按照这个思路, 如果num出现的bound我们不知道, 那么遇到有超出目前我们记录的maxFreq的时候, 我们就额外new一个stack, 来存达到这个maxFreq的值. 于是每一个num像是闯关一样, 如果来了相同的, 那么它们就能进入下一个freq所对应的stack.

我们用两个map, 一个用来记录num的频率, 另一个用来记录不同freq对应的stack, 同时也要有maxFreq来记录目前的最大freq是多少, 这样我们就能到相应的stack中取数字.

不同频率对应的stack记录着谁先后到达了该频率, 就好像一个数字到达一个频率后就会得到一个徽章, 这个徽章就存到了stack中不会变.

时间复杂度: O(1)
空间复杂度: O(n) 重复出现的数字在从1到其出现的频率对应的stack中都会出现. 那么等于所有的stack算是把所有的数字装起来了.