Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

• Example:

  1 2 3 4 5 6 7 8

  int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8

• Note:

  1	You may assume that nums' length ≥ k-1 and k ≥ 1.

求数组中的第K个最大值

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

static class  {
    final PriorityQueue<Integer> q;
    final int k;

    public (int k, int[] a) {
      this.k = k;
      q = new PriorityQueue<>(k);
      for (int n : a)
        add(n);
    }

    public int add(int n) {
      if (q.size() < k)
        q.offer(n);
      else if (q.peek() < n) {
        q.poll();
        q.offer(n);
      }
      return q.peek();
    }
  }

参考资料

• kth-largest-element-in-a-stream