[HackerRank]Java的雙向佇列(Java Dequeue)

題目描述

在電腦科學的領域，一個雙向佇列(double-ended queue, dequeue, deque)是一種佇列的抽象資料型態，雙向佇列中的每個元素都可以在佇列的最前端或最後端被新增移除。

Deque介面被許多集合類別所實作，像是LinkedList和ArrayDeque。舉例來說，雙向佇列的物件可以用以下方式宣告與實體化：

Deque deque = new LinkedList<>();

或

Deque deque = new ArrayDeque<>();

在這個題目中，您將會得到N個整數。您需要從任意大小為M的連續子陣列中找出其中最大的不同整數的數量。

原題網址

輸入格式

輸入第一行包含N和M兩個整數，分別表示整數的數量和子陣列的大小，範圍都在1到100000之間(包含1和100000)，M小於等於N。接下來的一行中，包含N個用空格分隔的整數，範圍在0到10000000之間(包含1和10000000)。

輸出格式

輸出所有子陣列中，最大的不重複整數數量。

範例輸入

範例輸出

額外解釋

所有子陣列如下：

s1=⟨5,3,5⟩，有2個不重複的整數。

s2=⟨3,5,2⟩，有3個不重複的整數。

s3=⟨5,2,3⟩，有3個不重複的整數。

s4=⟨2,3,2⟩，有2個不重複的整數。

所以最大不重複整數數量為3。

解題概念

一邊讀入整數一邊將整數存入Dequeue中，並且使用一個HashMap物件來儲存整數出現的次數。當Dequeue的數量大於或是等於m的時候，要先將最先放進Dequeue的元素取出，並且更改HashMap物件的計數內容，才可以再將整數存入Dequeue中。在每次讀入整數後更改HashMap物件的同時，順便去記錄目前出現次數的最大值。最後再將最大值輸出即可。

參考答案

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Scanner;

public class test {

    public static void main(final String[] args) {
        final Scanner in = new Scanner(System.in);
        final Deque<Integer> deque = new ArrayDeque<>();
        final int n = in.nextInt();
        final int m = in.nextInt();

        int maxUnique = 0;
        int uniqueSize = 0;
        final HashMap<Integer, Integer> counterMap = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            final int num = in.nextInt();
            if (deque.size() >= m) {
                final Integer pollNum = deque.pollLast();
                final int count = counterMap.get(pollNum);
                if (count == 1) {
                    counterMap.remove(pollNum);
                    --uniqueSize;
                } else {
                    counterMap.put(pollNum, count - 1);
                }
            }
            deque.addFirst(num);
            if (counterMap.containsKey(num)) {
                counterMap.put(num, counterMap.get(num) + 1);
            } else {
                counterMap.put(num, 1);
                ++uniqueSize;
                if (uniqueSize > maxUnique) {
                    maxUnique = uniqueSize;
                }
            }
        }
        System.out.println(maxUnique);
    }
}