895. 最大频率栈

895. 最大频率栈

class FreqStack {

    Map<Integer, Stack<Integer>> stk; //  k: 出现次数， v: 栈
    Map<Integer, Integer> cnt;  // k：数，  v：该数出现的个数
    int n; // 当前 个数的最大值


    public FreqStack() {
        stk = new HashMap<>();
        cnt = new HashMap<>();
        n = 0;
    }

    public void push(int val) {
        Integer valCnt = cnt.getOrDefault(val, 0); // val 出现的次数
        valCnt = valCnt + 1;    // 该 val 次数+1
        cnt.put(val, valCnt);   // 更新map
        Stack<Integer> stack = stk.get(valCnt); // 该次数对应的stack
        if (null == stack) stack = new Stack<>();
        stack.push(val);  // 更新stack
        stk.put(valCnt, stack);
        n = Math.max(n, valCnt);  // 更新当前个数的最大值
    }

    public int pop() {
        Stack<Integer> stack = stk.get(n);  // 当前个数最大值的stack
        Integer peek = stack.pop();         // 本次要pop的数
        Integer peekCnt = cnt.get(peek);
        peekCnt = peekCnt - 1;              // 该pop的数的次数-1
        cnt.put(peek, peekCnt);             // 更新map
        if (stack.isEmpty()) n--;           // 如果 当前个数最大值的stack 为空， 说明当前最大个数应该-1
        return peek;
    }
}