У вас есть простой массив, и вам нужно найти следующий наибольший элемент для каждого элемента. Насколько просто это звучит? Что ж, в тот момент, когда этот вопрос задают в интервью, вы обязательно увидите звезды, луну и даже Млечный путь. Такие простые вопросы могут сломить самые стойкие умы. И тому есть много причин.

Это связано с тем, что подобные проблемы имеют несколько решений, и самые простые методы легко доступны. Но именно эти оптимизированные решения имеют большое значение. В этом посте вы прочтете о самом простом и оптимизированном исправлении для поиска следующего лучшего элемента с использованием JavaScript.

Мощный цикл For

Несомненно, цикл for решает все проблемы. И эта «постановка задачи» не является исключением. Разберемся, как решается проблема с помощью цикла for.

Псевдокод с использованием цикла For

1. Перебрать каждый элемент в массиве

2. Перебрать каждый элемент после текущего элемента

3. Если элемент больше текущего элемента, отобразить и разорвать цикл

4. продолжайте шаги с 1 по 3, пока не будут пройдены все элементы массива

Фактические строки кода

Теперь настоящие строки кода, использующие цикл for, довольно просты. Мы начинаем с определения второго массива и инициализируем его значением «-1». Длина массива2 будет зависеть от «массива1». Мы используем for…in, который перебирает все перечисляемые свойства массива1. В этом случае индекс будет представлен. Упрощение инициализации array2.

let array1 = [4,5,1,7,2,19,0];
let array2 = [];
for(index in array1){
   array2[index] = -1
}

После инициализации массива2 мы можем запустить цикл for для массива1.

for(var i = 0; i < array1.length; i ++){
   for(var j = i+1; j < array1.length; j ++){
      if( array1[i]< array1[j] ){
         array2[i] = array1[j];
         break;
      }
   }
}
console.log(array2);

Для данного ввода выходные данные, хранящиеся в массиве2, будут такими: [5,7,7,19,19,-1,-1]

Вычисление временной сложности

давайте поймем, сколько времени уйдет на выполнение этих операций.

Для построения array2: Big O(n)

Для сравнения с использованием циклов for..for..: Большой O(n) * Большой O(n!) = Большой O(n²)

Общая временная сложность = большая O(n) + большая O(n²) = большая O(n²)

Оптимизированный подход

Приведенное выше решение может быть уменьшено до временной сложности Big O(n), только если используются правильные структуры данных. Здесь лучшей структурой данных будет «стек».

Псевдокод

1. Создайте массив, который будет выступать в качестве стека

2. Перебрать массив

3. Если текущий элемент меньше, чем элемент на вершине стека, поместите его в стек.

4. Если текущий элемент больше, чем элемент на вершине стека, извлекайте стек, пока вершина стека не станет меньше, чем текущий элемент.

5. Поместить текущий элемент в стек

6. Повторяйте шаги со 2 по 5, пока массив не станет пустым.

7. Если в стеке все еще есть элементы, у них нет следующего по величине элемента в массиве, поэтому выведите «NA»

Фактические строки кода

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

JavaScript, который делает реализацию еще проще. Например, вы можете воспроизвести поведение стека на массивах с помощью функций pop() и push(). pop() удаляет последний элемент стека. А push() вставляет элемент в конец массива. Это соответствует природе стека LIFO.

JavaScript также воспроизводит поведение очереди в массивах с помощью функций shift() и push(). shift() удаляет первый элемент в очереди. Как упоминалось ранее, вы можете использовать push() для вставки элемента в конец массива. Это соответствует характеру очередей FIFO.

Теперь давайте создадим наш код. Начнем с создания двух массивов. array1 содержит элементы для оценки. И мы создаем второй массив и называем его «стек».

var array1 = [4,3,6,19,20];
var stack = [];

Чтобы было немного интереснее, давайте определим нашу собственную функцию TopOfStack. Цель этой функции — вернуть последний введенный элемент в стеке.

Мы используем Function.prototype.bind() для управления «этим» функции TopOfStack(). В результате вам не нужно передавать какие-либо переменные в функцию.

let topOfStack = function(){
   let item = this[this.length - 1];
   return item;
}
//inside the findNextGreatestElement function
let getTopOfStack = topOfStack.bind(stack);

Функция findNextGreatestElement() будет выглядеть следующим образом:

findNextGreatestElement = function(){
  let getTopOfStack = topOfStack.bind(stack);
   for(item of array1){
       while(stack.length > 0 && item > getTopOfStack()){
           console.log(item +" " +getTopOfStack());
           stack.pop();
       }
       stack.push(item);
   }
   for(item of stack)
      console.log("NA" +" " +item)
}

Ну вот! Теперь мы сгенерировали следующий наибольший элемент для каждого элемента массива с помощью стека.

Вычисление временной сложности

Время перебора каждого элемента массива: большой O(n)

Время для получения вершины стека: Big O(1)

Общая временная сложность: Big O(n)

Вывод

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

Забрать домой

Ссылка на код в GitHub: https://github.com/CodeLearnDDev/basicJS.git; имя файла: nextGreatestElementInArray