предыдущий последний более крупный элемент в массиве

Question

Я пытаюсь решить следующую проблему. Учитывая массив действительных чисел [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1] для каждого элемента, мне нужно найти последний предыдущий более крупный элемент в массиве.

Например, нет ничего большего, чем первый элемент (7), поэтому он имеет NaN. Для второго элемента (2) 7 больше. Таким образом, в конце ответ выглядит так:

[NaN, 7, 7, NaN, 8, 8, 8, 8, 7, 4, 3, 1]. Конечно, я могу просто проверить все предыдущие элементы для каждого элемента, но это квадратично по количеству элементов массива.

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

Answer 1

Вот один из способов сделать это

create a stack which is initially empty 
for each number N in the array 
{ 
    while the stack is not empty 
    { 
     if the top item on the stack T is greater than N 
     { 
      output T (leaving it on the stack) 
      break 
     } 
     else 
     { 
      pop T off of the stack 
     } 
    } 
    if the stack is empty 
    { 
     output NAN 
    } 
    push N onto the stack 
} 

Берем массив образца [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1], вот как алгоритм ее разрешит.

stack   N    output 
-    7    NAN 
7    2    7 
7 2    4    7 
7 4    8    NAN 
8    1    8 
8 1    1    8 
8 1    6    8 
8 6    7    8 
8 7    4    7 
8 7 4   3    4 
8 7 4 3   1    3 

Теория состоит в том, что стек не должен содержать небольшие числа, так как они никогда не будут частью выхода. Например, в последовательности 7, 2, 4 2 не требуется, так как любое число меньше 2 также будет меньше 4. Следовательно, стек должен содержать только 7 и 4.

Сложность Анализ

Временная сложность алгоритма может быть показано, что O (N) следующим образом:

1. есть именно n толчки (каждое число во входном массиве - , толкается в стек один раз и только один раз)
2. не более n pops (после того, как номер выскочил из стека, она отбрасывается)
3. есть в большинстве n не удались сравнение (так как число извлекается и отбрасывал после неудачного сравнения)
4. есть самое n успешных сравнений (так как алгоритм переходит к следующему номеру в входной массив после успешного сравнения)
5. имеется ровно n операций вывода (так как алгоритм генерирует один выход для каждого числа во входном массиве)

Следовательно, мы заключаем, что алгоритм выполняет не более 5n операций для выполнения задачи, которая является временной сложностью O (n).

Answer 2

Почему бы просто не определить переменную 'current_largest' и перебрать ее через массив слева направо? У каждого элемента наибольший ток наибольший предыдущий, и если текущий элемент больше, присвойте current_largest текущему элементу. Затем перейдите к следующему элементу.

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

EDIT2: Мне кажется, что нынешний самый большой метод будет работать. Вам просто нужно записать current_largest, прежде чем назначить ему новое значение. Например, в Python:

current_largest = 0 
for current_element in elements: 
    print("Largest previous is "+current_largest) 
    if(current_element>current_largest): 
     current_largest = current_element 

Если вы хотите массив из них, а затем просто нажать значение массива вместо оператора печати.

Answer 3

В соответствии с моим лучшим пониманием вашего вопроса. Ниже приведено решение. Рабочий пример: JSFIDDLE

var item = document.getElementById("myButton"); 
item.addEventListener("click", myFunction); 
function myFunction() { 
    var myItems = [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1]; 
    var previousItem; 
    var currentItem; 
    var currentLargest; 
    for (var i = 0; i < myItems.length; i++) { 
     currentItem = myItems[i]; 
     if (i == 0) { 
      previousItem = myItems[0]; 
      currentItem = myItems[0]; 
      myItems[i] = NaN; 
     } 
     else { 
      if (currentItem < previousItem) { 
       myItems[i] = previousItem; 
       currentLargest = previousItem; 
      } 
      if (currentItem > currentLargest) { 
       currentLargest = currentItem; 
       myItems[i] = NaN; 
      } 
      else { 
       myItems[i] = currentLargest; 
      } 
      previousItem = currentItem; 
     } 
    } 
    var stringItems = myItems.join(","); 
    document.getElementById("arrayAnswer").innerHTML = stringItems; 
} 

Answer 4

Мы можем сохранить для каждого элемента массива индекс своего последнего более крупного элемента. Когда мы обрабатываем новый элемент x, мы проверяем предыдущий элемент y. Если y больше, то мы нашли то, что хотим. Если нет, мы проверяем, какой индекс является самым последним более крупным элементом y. Мы продолжаем, пока не найдем наш необходимый элемент и его индекс. Использование Python:

a = [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1] 
idx, result = [], [] 
for i, v in enumerate(a, -1): 
    while i >= 0 and v >= a[i]: 
     i = idx[i] 
    idx.append(i) 
    result.append(a[i] if i >= 0 else None) 

Результат:

[None, 7, 7, None, 8, 8, 8, 8, 7, 4, 3] 

Алгоритм является линейным. Когда индекс j безуспешно проверен, потому что мы ищем самый последний более крупный элемент индекса i > j, то отныне i укажет на меньший индекс, чем j, а j не будет проверяться снова.