545.Top k Largest Numbers II

1.Description(Medium)

Implement a data structure, provide two interfaces:

1. add(number). Add a new number in the data structure.

2. topk(). Return the top _k _largest numbers in this data structure. _k _is given when we create the data structure.

Example

s = new Solution(3);
>>create a new data structure.
s.add(3)
s.add(10)
s.topk()
>> return [10, 3]
s.add(1000)
s.add(-99)
s.topk()
>>return [1000, 10, 3]
s.add(4)
s.topk()
>> return [1000, 10, 4]
s.add(100)
s.topk()
>> return [1000, 100, 10]

2.Code

本题目要建立一个PriorityQueue.

最后Collections.sort(result, Collections.reverseOrder()); 去逆向排序一个arraylist.

public class Solution_545 {

    private Queue<Integer> minheap;//栈顶是最小的,存放最大的maxsize个数
    private int maxsize;//the size of priority queue


     public Solution_545(int k) {
            minheap=new PriorityQueue<Integer>();
            maxsize=k;
        }

        public void add(int num) {

            if(minheap.size()<maxsize){
                minheap.offer(num);
                return;
            }

            if(num>minheap.peek()){
                minheap.poll();
                minheap.offer(num);
            }

        }

        //find largest k
        public List<Integer> topk() {

            List<Integer> result=new ArrayList<Integer>();
            Iterator<Integer> it=minheap.iterator();
            while(it.hasNext()){
                result.add(it.next());
            }

            Collections.sort(result, Collections.reverseOrder());  //use to reverse the arraylist
            return result;            
        }

}