leetcode-go/written-exam/ebay-2019-autumn/no2/Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
        int[] a = new int[k];
        for (int i = 0; i < k; i++) {
            a[i] = in.nextInt();
        }
        in.close();
        System.out.println(main.solve(n, m, a));
    }

    public int solve(int n, int m, int[] a) {
        int[] prev = new int[n + 1];
        int[] next = new int[a.length + 1];
        Arrays.fill(prev, a.length);
        for (int i = 0; i < a.length; i++) {
            next[i] = a.length;
            next[prev[a[i]]] = i;
            prev[a[i]] = i;
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] rem = new boolean[n + 1];
        int size = 0, ans = 0;
        for (int i = 0; i < a.length; i++) {
            if (rem[a[i]]) {
                pq.add(new Node(a[i], next[i]));
                continue;
            }
            if (size == m) {
                size--;
                while (!pq.isEmpty()) {
                    Node top = pq.poll();
                    if (rem[top.x]) {
                        rem[top.x] = false;
                        break;
                    }
                }
            }
            size++;
            ans++;
            rem[a[i]] = true;
            pq.add(new Node(a[i], next[i]));
        }
        return ans;
    }
}

class Node implements Comparable<Node> {
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Node that) {
        return that.y - this.y;
    }
}