最小栈 & 最大栈

155. 最小栈

895. 最大频率栈

最小栈

思路：维护一个调用push()每个元素后的最小值栈

xxxxxxxxxx
class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()) minStack.push(val);
        else if (getMin() <= val) minStack.push(getMin());
        else if (getMin() > val) minStack.push(val);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

最大栈

xxxxxxxxxx
public class FreqStack {
    // 记录最大频率
    private int maxFreq;
    // 记录每个元素的频率
    private Map<Integer, Integer> valToFreq;
    // 记录某一频率的所有元素
    private Map<Integer, Stack<Integer>> freqToVal;

    public FreqStack() {
        maxFreq = 0;
        valToFreq = new HashMap<>();
        freqToVal = new HashMap<>();
    }

    public void push(int val) {
        // 获得 val 的频率
        int freq = valToFreq.getOrDefault(val, 0) + 1;
        // 更新 val to freq
        valToFreq.put(val, freq);
        // 更新 freq to val
        freqToVal.putIfAbsent(freq, new Stack<>());
        freqToVal.get(freq).push(val);
        // 更新 maxFreq
        maxFreq = Math.max(maxFreq, freq);
    }

    public int pop() {
        // 弹出一个频率最大的元素
        Stack<Integer> valStack = freqToVal.get(maxFreq);
        int v = valStack.pop();
        // 更新 val to freq
        valToFreq.put(v, valToFreq.get(v) - 1);
        // 更新 maxFreq
        if (valStack.isEmpty()) {
            maxFreq--;
        }
        return v;
    }
}