Как найти максимум каждого подмассива некоторой фиксированной заданной длины в данном массиве

Question

Нам дан массив из n элементов и целое число k.Предположим, что мы хотим сдвинуть окно длины k по массиву, сообщив о наибольшем значении, содержащемся в каждом окне.Например, учитывая массив

15  10   9  16  20  14  13

Учитывая окно длины 4, мы бы вывели

[15  10   9  16] 20  14  13   ---> Output 16
 15 [10   9  16  20] 14  13   ---> Output 20
 15  10 [ 9  16  20  14]  13  ---> Output 20
 15  10   9 [16  20  14  13]  ---> Output 20

Таким образом, результат будет

16  20  20  20

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

Кто-нибудь знает эффективный алгоритм для решения этой проблемы?

Answer 1

Этот старый вопрос описывает, как построить структуру данных очереди, поддерживающую операции вставки, удаления из очереди и поиска минут за все время O (1).Обратите внимание, что это не стандартная очередь приоритетов, но вместо этого это очередь, в которой в любой момент вы можете найти значение наименьшего элемента, который он содержит за время O (1).Вы можете легко изменить эту структуру для поддержки find-max в O (1) вместо find-min, так как это больше относится к данной конкретной проблеме.

Используя эту структуру, вы можете решить эту проблему в O (n) время следующим образом:

1. Поместить первые k элементов массива в специальную очередь.
2. Для каждого элемента в остальной части массива:
   1. Использоватьоперация find-max очереди, чтобы сообщить о самом большом элементе текущего поддиапазона.
   2. Удалить элемент из очереди, оставив на месте последние k-1 элементов старого диапазона.
   3. Постановить в очередьследующий элемент из последовательности, в результате чего очередь теперь содержит следующий поддиапазон k-элемента последовательности.

Это занимает в общей сложности O (n) времени, так какВы посещаете каждый элемент массива один раз, ставя в очередь и удаляя каждый из них не более одного раза, и вызываете find-max ровно nk раз.Я думаю, что это довольно круто, поскольку сложность не зависит от k , что поначалу не кажется обязательным.

Надеюсь, это поможет!И спасибо, что задали крутой вопрос!

Answer 2

Вы можете достичь сложности O (n), используя Двусторонняя очередь .

Вот реализация C #

    public static void printKMax(int[] arr, int n, int k)
    {
        Deque<int> qi = new Deque<int>();
        int i;
        for (i=0;i< k; i++) // first window of the array
        {
            while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()]))
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        for(i=k ;i< n; ++i)
        {
            Console.WriteLine(arr[qi.PeekFront()]); // the front item is the largest element in previous window.
            while (qi.Count > 0 && qi.PeekFront() <= i - k) // this is where the comparison is happening!
            {
                qi.PopFront(); //now it's out of its window k 
            }
            while(qi.Count>0 && arr[i]>=arr[qi.PeekBack()]) // repeat
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        Console.WriteLine(arr[qi.PeekFront()]);
    }

Answer 3

Лучшее, что я могу быстро придумать, это O (n log m). Вы можете получить это путем динамического программирования.

В первом проходе вы найдете максимум для каждого элемента максимум из самого элемента и следующего.

Теперь у вас есть n максимумов (размер окна = 2).

Теперь вы можете найти в этом массиве максимум от каждого элемента и последующий текст в этом массиве (дает вам для каждого элемента максимум для следующих 4, т.е. размер окна = 4).

Затем вы можете сделать это снова и снова (и каждый раз, когда размер окна удваивается).

Как ясно видно, размер окна растет в геометрической прогрессии.

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

Answer 4

Вы можете продолжить поиск в табу:

Прокрутите список и получите максимум 4 первого i-го элемента. Затем на следующем шаге просто проверьте, превосходит ли i + 1-й элемент максимум максимума предыдущих элементов

• если i + 1> = предыдущий максимум, то новый максимум = i + 1 повторно установить табу
• если i + 1 <предыдущий максимум, то если предыдущий максимум был найден меньше N шаг назад сохранить предыдущий (вот табу) </li>
• если i + 1 <предыдущий максимум и предыдущий максимум равен табу, тогда возьмите новый максимум 4 я + 1-й элементы. </li>

Я не уверен, что это понятно, но скажите мне, если у вас есть какие-либо вопросы. ниже приведен код на python для его проверки.

l=[15,10,9,16,20,14,13,11,12]
N=4
res=[-1] #initialise res
tabu=1  #initialise tabu
for k in range(0,len(l)):
#if the previous element res[-1] is higher than l[k] and not tabu then keep it
#if the previous is tabu and higher than l[k] make a new search without it
#if the previous is smaller than l[k] take the new max =l[k]

    if l[k]<res[-1] and tabu<N:
        tabu+=1
        res.append(res[-1])
    elif l[k] < res[-1] and tabu == N:
         newMax=max(l[k-N+1:k+1])
         res.append(newMax)
         tabu=N-l[k-N+1:k+1].index(newMax) #the tabu is initialized depending on the position of the newmaximum
    elif l[k] >= res[-1]:
        tabu=1
        res.append(l[k])

print res[N:] #take of the N first element

Сложность:

Я обновил код thx до flolo и сложности. это больше не O (N), а O (M * N)

Худший случай, когда вам нужно пересчитать максимум на каждом шаге цикла. например, список строго уменьшается.

на каждом шаге цикла необходимо пересчитать максимум M элементов

тогда общая сложность составляет O (M * N)

Answer 5

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

Таким образом, выберите максимум (элемент max в подразделе) будет стоить O (logL) времени, где L - длина текущего подраздела; добавить новый также будет O (logL). Чтобы удалить самый старый, просто найдите значение и уменьшите счет на 1, если счет идет к 0, удалите его.

Таким образом, общее время будет O (NlogL), где N - длина массива.

Answer 6

Пожалуйста, просмотрите мой код.По моему мнению, сложность времени для этого алгоритма составляет

O (l) + O (n)

    for (int i = 0; i< l;i++){
        oldHighest += arraylist[i];
    }
    int kr = FindMaxSumSubArray(arraylist, startIndex, lastIndex);



    public static int FindMaxSumSubArray(int[] arraylist, int startIndex, int lastIndex){

    int k = (startIndex + lastIndex)/2;
    k = k - startIndex;
    lastIndex = lastIndex  - startIndex;

    if(arraylist.length == 1){
        if(lcount<l){
            highestSum += arraylist[0];
            lcount++;
        }
        else if (lcount == l){
            if(highestSum >= oldHighest){
                oldHighest = highestSum;
                result = count - l + 1;
            }
            highestSum = 0;
            highestSum += arraylist[0];
            lcount = 1;
        }
        count++;
        return result;
    }

    FindMaxSumSubArray(Arrays.copyOfRange(arraylist, 0, k+1), 0, k);
    FindMaxSumSubArray(Arrays.copyOfRange(arraylist, k+1, lastIndex+1), k+1, lastIndex);

    return result;
 }

Я не понимаю, если этолучше делать в рекурсии или просто линейно?