Как сохранить скользящее окно min для несортированного массива? [Дубликат]

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

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

Поскольку каждый элемент находится в очереди и выгружается с максимальной сложности времени от времени, то O (n + n) = O (2n) = O (n). И размер очереди не может превышать предел k. поэтому пространственная сложность = O (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. Для ввода образца: [/g1]
3. Мы разделили на блоки, потому что мы рассчитаем максимум двумя способами A.), пройдя слева направо B.), пройдя справа налево , но как?
4. Во-первых, перемещение слева направо. Для каждого элемента ai в блоке мы найдем максимум до тех пор, пока этот элемент ai не начнет от START блока до END этого блока. Итак, здесь [/g2]
5. Во-вторых, перемещение справа налево. Для каждого элемента 'ai' в блоке мы найдем максимум до тех пор, пока этот элемент 'ai' не станет от END блока до START этого блока. Итак, [/g3]
6. Теперь нам нужно найти максимум для каждого подмассива или окна размера «W». Итак, начиная с индекса = 1 до индекса = N-W + 1. max_val[index] = max(RL[index], LR[index+w-1]); [/g4]

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

Запуск кода Link

---

Я попытаюсь доказать: (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] )

Вот реализация 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 * log(k)). Я не уверен, что это будет лучше.

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

Используя кучку Фибоначчи, вы можете сделать это в 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)

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

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

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

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

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

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

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

1)

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

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

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

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

Сравните первые 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

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

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

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

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)

Просто обратите внимание, что вам нужно только найти в новом окне, если: * Новый элемент в окне меньше предыдущего (если он больше, это точно). OR * Элемент, который только что выскочил из окна, был больше.

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

Вот решение в 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]);
        }
    }

}

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 (1). https://github.com/varoonverma/code-challenge.git