这就是你心心念念的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();
*/