Java Queue & TreeMap Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need last m elements -> we use queue to record last m elements\nWe need to remove k 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need last m elements -> we use queue to record last m elements\nWe need to remove k smallest and k largest\n1. total number of elements to be added is m - 2 * k\n2. Use TreeMap to remove k smallest\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAdd\n1. Whenever we add a number, we check if the size of the queue is larger than m. If the size is larger than m, we remove the first element in the queue.\n2. Meanwhile we maintain our TreeMap\n\nQuery\n1. Main 2 fields, one is how many ksmallest we have skipped, the other is how many elements we have added.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n * log n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m)\n# Code\n```java []\nclass MKAverage {\n    int m, k;\n    Queue<Integer> q;\n    TreeMap<Integer, Integer> tm; \n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        q = new ArrayDeque<>();\n        tm = new TreeMap<>();\n    }\n    \n    public void addElement(int num) {\n        q.offer(num);\n        tm.put(num, tm.getOrDefault(num, 0) + 1);\n        if (q.size() > m) {\n            int polled = q.poll();\n            int count = tm.get(polled);\n            if (count == 1) \n                tm.remove(polled);\n            else\n                tm.put(polled, count - 1);\n        } \n    }\n    \n    public int calculateMKAverage() {\n        if (q.size() < m) return -1;\n        long sum = 0;\n        int added = 0;\n        int ksmall = 0;\n        int total = m - (2 * k);\n        for (int i : tm.keySet()) {\n            int count = tm.get(i);\n            int remove = Math.min(k - ksmall, count);\n            ksmall += remove;\n            count -= remove;\n            int add = Math.min(total - added, count);\n            sum += i * add;\n            added += add;\n            if (added == total) break;\n        }\n        return (int) sum / (m - 2 * k);\n    }\n}\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage obj = new MKAverage(m, k);\n * obj.addElement(num);\n * int param_2 = obj.calculateMKAverage();\n */\n```
['Java']