Trouver le maximum pour chaque fenêtre de taille k dans un tableau

Question

Étant donné un tableau de taille n et k, comment trouvez-vous le maximum pour chaque sous-tableau contigu de taille k ?

Par exemple

 arr = 1 5 2 6 3 1 24 7
k = 3
ans = 5 6 6 6 24 24

Je pensais avoir un tableau de taille k et chaque étape expulser le dernier élément et ajouter le nouvel élément et trouver le maximum parmi cela. Cela conduit à un temps d'exécution de O(nk). Y a-t-il une meilleure manière de faire cela?

Answer 1

Voici l'implémentation Java

 public static Integer[] maxsInEveryWindows(int[] arr, int k) {
    Deque<Integer> deque = new ArrayDeque<Integer>();
    /* Process first k (or first window) elements of array */
    for (int i = 0; i < k; i++) {
        // For very element, the previous smaller elements are useless so
        // remove them from deque
        while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
            deque.removeLast(); // Remove from rear
        }
        // Add new element at rear of queue
        deque.addLast(i);
    }
    List<Integer> result = new ArrayList<Integer>();
    // Process rest of the elements, i.e., from arr[k] to arr[n-1]
    for (int i = k; i < arr.length; i++) {
        // The element at the front of the queue is the largest element of
        // previous window, so add to result.
        result.add(arr[deque.getFirst()]);
        // Remove all elements smaller than the currently
        // being added element (remove useless elements)
        while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
            deque.removeLast();
        }
        // Remove the elements which are out of this window
        while (!deque.isEmpty() && deque.getFirst() <= i - k) {
            deque.removeFirst();
        }
        // Add current element at the rear of deque
        deque.addLast(i);
    }
    // Print the maximum element of last window
    result.add(arr[deque.getFirst()]);

    return result.toArray(new Integer[0]);
}

Voici le cas de test correspondant

 @Test
public void maxsInWindowsOfSizeKTest() {
    Integer[] result = ArrayUtils.maxsInEveryWindows(new int[]{1, 2, 3, 1, 4, 5, 2, 3, 6}, 3);
    assertThat(result, equalTo(new Integer[]{3, 3, 4, 5, 5, 5, 6}));

    result = ArrayUtils.maxsInEveryWindows(new int[]{8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, 4);
    assertThat(result, equalTo(new Integer[]{10, 10, 10, 15, 15, 90, 90}));
}