Нахождение максимума для каждого окна размера k в массиве

Вы слышали о том, как это делается в O (n) с помощью dequeue.

Хорошо, что это хорошо известный алгоритм для этого вопроса, чтобы сделать в O (n). Метод, о котором я говорю, довольно прост, требует динамического программирования и имеет временную сложность O(n).

Your Sample Input:
n=10 , W = 3

10 3
1 -2 5 6 0 9 8 -1 2 0

Answer = 5 6 6 9 9 9 8 2

Понятие: Динамическое Программирование

Алгоритм:

1. N-количество элементов в массиве, а W-размер окна. Итак, номер окна = N-W+1

2. Теперь разделим массив в блоки W, начиная с индекса 1.

   Здесь разделите на блоки размером 'W'=3. Для вашего примера ввода:

   

3. Мы разделились на блоки, потому что будем вычислять максимум двумя способами: а) путем обхода слева направо; б) путем обхода справа налево. но как это сделать ??

4. Во-первых, переход слева направо. Для каждого элемента ai в блоке мы найдем максимум до этого элемента ai, начиная от начала блока до конца блока. этот блок. Так вот,

   

5. Во-вторых, пересекая справа налево. Для каждого элемента 'ai' в блоке мы найдем максимум до этого элемента 'ai', начиная с конца блока до начала этого блока. Так Вот,

   

6. Теперь мы должны найти максимум для каждого подмногообразия или окна размера 'W'. Итак, начиная с индекса = 1 до индекса = N-W+1 .

   max_val[index] = max(RL[index], LR[index+w-1]);

   

    for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5
   

Симлиарно, для всех индексов i, (i<=(n-k+1)), значение в RL[i] и LR[i+w-1] сравниваются, и максимум среди этих двух является ответом для этого подмножества.

Итак, Окончательный Ответ : 5 6 6 9 9 9 8 2

Временная сложность: O (n)

Код реализации:

// Shashank Jain
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LIM 100001 

using namespace std;

int arr[LIM]; // Input Array
int LR[LIM]; // maximum from Left to Right
int RL[LIM]; // maximum from Right to left
int max_val[LIM]; // number of subarrays(windows) will be n-k+1

int main(){
    int n, w, i, k; // 'n' is number of elements in array
                    // 'w' is Window's Size 
    cin >> n >> w;

    k = n - w + 1; // 'K' is number of Windows

    for(i = 1; i <= n; i++)
        cin >> arr[i];

    for(i = 1; i <= n; i++){ // for maximum Left to Right
        if(i % w == 1) // that means START of a block
            LR[i] = arr[i];
        else
            LR[i] = max(LR[i - 1], arr[i]);        
    }

    for(i = n; i >= 1; i--){ // for maximum Right to Left
        if(i == n) // Maybe the last block is not of size 'W'. 
            RL[i] = arr[i]; 
        else if(i % w == 0) // that means END of a block
            RL[i] = arr[i];
        else
            RL[i] = max(RL[i+1], arr[i]);
    }

    for(i = 1; i <= k; i++)    // maximum
        max_val[i] = max(RL[i], LR[i + w - 1]);

    for(i = 1; i <= k ; i++)
        cout << max_val[i] << " ";

    cout << endl;

    return 0;
}  

Запуск Кодовой Ссылки

---

Я попытаюсь доказать: (by @johnchen902)

Если k % w != 1 (k не является началом блока)

Let k* = The begin of block containing k
ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = max( max( arr[k],  arr[k + 1],  arr[k + 2],  ..., arr[k*]), 
              max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) )
       = max( RL[k], LR[k+w-1] )

В противном случае (k является началом блока)

ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = RL[k] = LR[k+w-1]
       = max( RL[k], LR[k+w-1] )

Подход к динамическому программированию очень точно объяснен Шашанком Джайном. Я хотел бы объяснить, как сделать то же самое с помощью dequeue. Ключ состоит в том, чтобы сохранить максимальный элемент в верхней части очереди (для окна) и отбросить ненужные элементы , а также нам нужно отбросить элементы, которые находятся вне индекса текущего окна.
бесполезные элементы = Если текущий элемент больше, чем последний элемент очереди, то последний элемент очереди бесполезен. .
Примечание: мы храним индекс в очереди, а не сам элемент. Это будет более ясно из самого кода.
1. Если текущий элемент больше, чем последний элемент очереди, то последний элемент очереди бесполезен . Нам нужно удалить этот последний элемент. (и продолжайте удалять, пока последний элемент очереди не станет меньше текущего элемента).
2. Если if current_index-k >= q. front (), это означает, что мы выходим из окна, поэтому нам нужно удалить элемент из front of очередь.

vector<int> max_sub_deque(vector<int> &A,int k)
{
    deque<int> q;
    for(int i=0;i<k;i++)
    {
        while(!q.empty() && A[i] >= A[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    vector<int> res;
    for(int i=k;i<A.size();i++)
    {
        res.push_back(A[q.front()]);
        while(!q.empty() && A[i] >= A[q.back()] )
            q.pop_back();
        while(!q.empty() && q.front() <= i-k)
            q.pop_front();
        q.push_back(i); 
    }
    res.push_back(A[q.front()]);
    return res;
}

Поскольку каждый элемент ставится в очередь и снимается с очереди atmost 1 раз, сложность
O(n+n) = O(2n) = O(n).
И размер очереди не может превышать предел к. Итак, сложность пространства = O (k).

Решение о(n) времени возможно путем объединения двух классических вопросов интервью:

• Создайте структуру данных стека (называемую MaxStack), которая поддерживает push, pop и max за O(1) Время.
  

  Это можно сделать с помощью двух стеков, второй из которых содержит минимум, видимый до сих пор.

• Смоделируйте очередь со стеком.
  

  Это можно сделать с помощью двух стеков. Помещает в одну стопку, и извлекает из другого.

Для эта проблема, нам в основном нужна очередь, которая поддерживает enqueue, dequeue и max в O (1) (амортизированное) время.

Мы объединяем вышеперечисленные два, моделируя очередь с двумя MaxStacks.

Чтобы решить вопрос, мы ставим в очередь k элементов, запрашиваем max, dequeue, enqueue k+1-й элемент, запрашиваем max и т. д. Это даст вам максимальное значение для каждого поддерева k-го размера.

Я думаю, что есть и другие решения.

1)

Я считаю, что идея очереди может быть упрощена. Мы поддерживаем а очереди и максимум для каждого K. Мы добавляет новый элемент, и dequeu все элементы, которые не больше, чем новый элемент.

2) поддерживать два новых массива, которые поддерживают текущий максимум для каждого блока k, один массив для одного направления (слева направо/справа налево).

3) используйте молоток: предварительная обработка за O(n) время для запросов максимального диапазона.

1) решение, приведенное выше, может быть наиболее оптимальным.

Используя кучу (или дерево), вы должны быть в состоянии сделать это в O(n * log(k)). Я не уверен, что это было бы действительно лучше.

Вот реализация 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]);
}

Вот соответствующий тестовый случай

@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}));
}

Используя кучу Фибоначчи, вы можете сделать это в O(n + (n-k) log k), которая равна O(n log k) для малых k, для k близких к n это становится O(n).

Алгоритм: на самом деле вам нужно:

• n вставки в кучу
• n-k удаления
• n-k findmax'S

Сколько стоят эти операции в кучах Фибоначчи ? Вставка и findmax амортизируется O(1), удаление амортизируется O(log n). Итак, у нас есть

O(n + (n-k) log k + (n-k)) = O(n + (n-k) log k)

Извините, это должен был быть комментарий, но я не могу комментировать сейчас. @Лео @глины Годдард Вы можете спасти себя от повторного вычисления максимума на storing both maximum and 2nd maximum of the window in the beginning (2-й максимум будет максимальным только в том случае, если в начальном окне есть два максимума). Если максимум ускользнет из окна, у вас все еще есть следующий лучший кандидат для сравнения с новой записью. Таким образом, вы получаете O(n), в противном случае, если бы вы разрешили все повторное вычисление снова, наихудший порядок был бы O (nk), k-окно размер.

class MaxFinder
{
    // finds the max and its index
    static int[] findMaxByIteration(int arr[], int start, int end)
    {
        int max, max_ndx; 

        max = arr[start];
        max_ndx = start;
        for (int i=start; i<end; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
                max_ndx = i;
            }    
        }

        int result[] = {max, max_ndx};

        return result;
    }

    // optimized to skip iteration, when previous windows max element 
    // is present in current window
    static void optimizedPrintKMax(int arr[], int n, int k)
    {
        int i, j, max, max_ndx;

        // for first window - find by iteration.    
        int result[] = findMaxByIteration(arr, 0, k);

        System.out.printf("%d ", result[0]);

        max = result[0];
        max_ndx = result[1];   

         for (j=1; j <= (n-k); j++)
         {
            // if previous max has fallen out of current window, iterate and find
            if (max_ndx < j)  
            {
                result = findMaxByIteration(arr, j, j+k);
                max = result[0];
                max_ndx = result[1];   
            } 
            // optimized path, just compare max with new_elem that has come into the window 
            else 
            {
                int new_elem_ndx = j + (k-1);
                if (arr[new_elem_ndx] > max)
                {
                    max = arr[new_elem_ndx];
                    max_ndx = new_elem_ndx;
                }      
            }

            System.out.printf("%d ", max);
         }   
    }     

    public static void main(String[] args)
    {
        int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        //int arr[] = {1,5,2,6,3,1,24,7};
        int n = arr.length;
        int k = 3;
        optimizedPrintKMax(arr, n, k);
    }
}    

package com;
public class SlidingWindow {

    public static void main(String[] args) {

        int[] array = { 1, 5, 2, 6, 3, 1, 24, 7 };
        int slide = 3;//say
        List<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < array.length - (slide-1); i++) {
            result.add(getMax(array, i, slide));

        }
        System.out.println("MaxList->>>>" + result.toString());
    }

    private static Integer getMax(int[] array, int i, int slide) {

        List<Integer> intermediate = new ArrayList<Integer>();
        System.out.println("Initial::" + intermediate.size());
        while (intermediate.size() < slide) {
            intermediate.add(array[i]);
            i++;
        }
        Collections.sort(intermediate);
        return intermediate.get(slide - 1);
    }
}

Здесь решение в O (n) временной сложности с вспомогательным deque

public class TestSlidingWindow {

    public static void main(String[] args) {
        int[] arr = { 1, 5, 7, 2, 1, 3, 4 };
        int k = 3;

        printMaxInSlidingWindow(arr, k);

    }

    public static void printMaxInSlidingWindow(int[] arr, int k) {

        Deque<Integer> queue = new ArrayDeque<Integer>();
        Deque<Integer> auxQueue = new ArrayDeque<Integer>();

        int[] resultArr = new int[(arr.length - k) + 1];

        int maxElement = 0;
        int j = 0;
        for (int i = 0; i < arr.length; i++) {

            queue.add(arr[i]);

            if (arr[i] > maxElement) {
                maxElement = arr[i];
            }

    /** we need to maintain the auxiliary deque to maintain max element  in case max element is removed. 
        We add the element to deque straight away if subsequent element is less than the last element
        (as there is a probability if last element is removed this element can be max element) otherwise 
        remove all lesser element then insert current element **/

            if (auxQueue.size() > 0) {
                if (arr[i] <  auxQueue.peek()) {
                    auxQueue.push(arr[i]);
                } else {
                    while (auxQueue.size() > 0 && (arr[i] >  auxQueue.peek())) {
                        auxQueue.pollLast();
                    }

                    auxQueue.push(arr[i]);
                }
            }else {
                auxQueue.push(arr[i]);
            }

            if (queue.size() > 3) {
                int removedEl = queue.removeFirst();
                if (maxElement == removedEl) {
                    maxElement = auxQueue.pollFirst();
                }
            }

            if (queue.size() == 3) {
                resultArr[j++] = maxElement;
            }

        }

        for (int i = 0; i < resultArr.length; i++) {
            System.out.println(resultArr[i]);
        }
    }

}

    static void countDistinct(int arr[], int n, int k) 
    { 
        System.out.print("\nMaximum integer in the window : ");
        // Traverse through every window
        for (int i = 0; i <= n - k; i++) {
               System.out.print(findMaximuminAllWindow(Arrays.copyOfRange(arr, i, arr.length), k)+ " ");
           }
    } 

    private static int findMaximuminAllWindow(int[] win, int k) {
        // TODO Auto-generated method stub
        int max= Integer.MIN_VALUE;

        for(int i=0; i<k;i++) {
            if(win[i]>max)
                max=win[i];
        }

        return max;
    }

Просто обратите внимание, что вам нужно только найти в новом окне, если: * Новый элемент в окне меньше предыдущего (если он больше, то наверняка этот). ОПЕРАЦИОННАЯ * Элемент, который только что выскочил из окна, был больше тока.

В этом случае повторите сканирование окна.

Полное рабочее решение в амортизированной константе O (1) сложности. https://github.com/varoonverma/code-challenge.git

Я создал простое решение, которое не нуждается в причудливых вещах. Идея состоит в том, чтобы отслеживать максимум из предыдущего окна и обновлять его только тогда, когда это необходимо.

void printKMax(int arr[], int n, int k)
{
    int max = arr[0];

    // find max of initial k elements.
    for (int i = 1; i < k; i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    printf("%d ", max);

    for (int i = k; i < n; i++) {
        if (arr[i] > max) // Compare it with just next element.
            max = arr[i];
        printf("%d ", max);
    }
}

Я не понял, есть ли у них какие-то проблемы с этим кодом, почему это никому не пришло в голову. Сложность времени = > O (n)

Для какой величины k? для разумного размера k. вы можете создать K буферов размера k и просто перебирать массив, отслеживая максимальное количество указателей элементов в буферах - не требует структур данных и является o (n) K^2 предварительным выделением.

Сравните первые k элементов и найдите максимальное, это ваше первое число

Затем сравните следующий элемент с предыдущим max. Если следующий элемент больше, то это ваш Макс следующего подмассива, если он равен или меньше, то макс для этого подмассива тот же

Затем переходим к следующему номеру

max(1 5 2) = 5
max(5 6) = 6
max(6 6) = 6
... and so on
max(3 24) = 24
max(24 7) = 24

Это лишь немного лучше, чем ваш ответ