Skip to content

895. Maximum Frequency Stack

895. Maximum Frequency Stack

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

难度: Hard

题意：

  1. 一个特殊的类栈数据结构，具有两种操作
  2. push x：表示将x入栈
  3. pop：表示将栈中最多的数弹出，相同数量的数弹出最近入栈的一个数

思路：

  • 这个题的数据结构中，x是key，既需要根据x来操作，又需要根据x的数量和入栈时间来出栈，典型的双向查找表

  • 维护一个x到x的入栈时间的映射关系，入栈时间我们定义为第几次push操作，即x->[t1,t2,t3]

  • 维护一个有序的x的入栈时间到x的对应表，比较函数定义为：栈中元素个数，和栈顶时间

代码：

class FreqStack {

    int _count;
    private class Item implements Comparable<Item> {
        LinkedList<Integer> time;

        public Item(LinkedList<Integer> time) {
            this.time = time;
        }

        public LinkedList<Integer> getTime() {
            return time;
        }

        @Override
        public int compareTo(Item o) {
            if (time.size() == o.time.size()) {
                return Integer.compare(o.time.getLast(), time.getLast());
            } else {
                return Integer.compare(o.time.size(), time.size());
            }
        }
    }

    TreeMap<Item, Integer> freqToId;
    Map<Integer, Item>  idToFreq;

    public FreqStack() {
        _count = 0;
        freqToId = new TreeMap<Item, Integer>();
        idToFreq = new HashMap<Integer, Item>();
    }

    public void push(int x) {
        if (!idToFreq.containsKey(x)) {
            LinkedList<Integer> time = new LinkedList<Integer>();
            time.addLast(_count++);
            Item item = new Item(time);
            freqToId.put(item, x);
            idToFreq.put(x, item);
        } else {
            Item origin = idToFreq.get(x);
            freqToId.remove(origin);
            LinkedList<Integer> time = origin.time;
            time.addLast(_count++);
            Item item = new Item(time);
            idToFreq.put(x, item);
            freqToId.put(item, x);
        }
    }

    public int pop() {
        Map.Entry<Item, Integer> first = freqToId.firstEntry();
        freqToId.remove(first.getKey());
        idToFreq.remove(first.getValue());

        LinkedList<Integer> time = first.getKey().time;
        time.removeLast();
        if (time.size() != 0) {
            Item item = new Item(time);
            idToFreq.put(first.getValue(), item);
            freqToId.put(item, first.getValue());
        }

        return first.getValue();
    }
}
回到顶部