Test.java

import java.util.*;
import java.util.stream.Collectors;
import com.google.common.collect.SortedMultiset;
import com.google.common.collect.TreeMultiset;

class Test {
  static List<Integer> solvePriorityQueue(List<Integer> list, int m) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(list.subList(0, m));
    List<Integer> res = new ArrayList<>(list.size() - m + 1);
    Integer mth = pq.peek();
    res.add(mth);
    for (int i : list.subList(m, list.size())) {
      if (i > mth) {
        pq.add(i);
        pq.poll();
        mth = pq.peek();
      }
      res.add(mth);
    }
    return res;
  }

  static List<Integer> solveSortedMultiset(List<Integer> list, int m) {
    List<Integer> result = new ArrayList<>(list.size() - m + 1);
    SortedMultiset<Integer> largest = list.subList(0, m).stream()
        .collect(Collectors.toCollection(TreeMultiset::create));
    result.add(largest.firstEntry().getElement());

    for (Integer element : list.subList(m, list.size())) {
      Integer firstElement = largest.firstEntry().getElement();
      if (element <= firstElement) {
        result.add(firstElement);
      } else {
        largest.remove(firstElement);
        largest.add(element);
        result.add(largest.firstEntry().getElement());
      }
    }
    return result;
  }

  public static void main(String... args) {
    int n = 1000000;
    int m = 50000;
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < n; ++i)
      list.add(i + 1);
    Collections.shuffle(list);

    List<Integer> a = solvePriorityQueue(list, m);
    List<Integer> b = solveSortedMultiset(list, m);
    if (!a.equals(b))
      throw new RuntimeException();

    for (int repeats = 0; repeats < 10; ++repeats) {
      long start = System.currentTimeMillis();
      List<Integer> c = solvePriorityQueue(list, m);
      long elapsed = System.currentTimeMillis() - start;
      System.out.println("solvePriorityQueue() " + elapsed + " ms");
      if (!c.equals(a))
        throw new RuntimeException();
    }

    for (int repeats = 0; repeats < 10; ++repeats) {
      long start = System.currentTimeMillis();
      List<Integer> c = solveSortedMultiset(list, m);
      long elapsed = System.currentTimeMillis() - start;
      System.out.println("solveSortedMultiset() " + elapsed + " ms");
      if (!c.equals(a))
        throw new RuntimeException();
    }
  }
}