Введение Задача «Ближайший больший элемент слева» (NGEL) — это классическая алгоритмическая задача, которая требует от нас найти ближайший элемент слева от каждого элемента в массиве, который больше, чем текущий элемент. В этой статье мы подробно обсудим проблему NGEL и предоставим практическую реализацию алгоритма на JavaScript.
Алгоритмический подход Алгоритмический подход к решению проблемы NGEL включает использование стековой структуры данных для отслеживания более крупных элементов, наблюдаемых до сих пор. Мы инициализируем пустой стек и перебираем массив слева направо. Для каждого элемента мы будем выталкивать элементы из стека, пока не найдем элемент больше, чем текущий элемент, или стек не станет пустым. Ближайший больший элемент слева от текущего элемента равен верхнему элементу стека. Если такого элемента не существует, ближайший больший элемент слева от текущего элемента равен -1. Затем мы поместим текущий элемент в стек. Этот процесс будет продолжаться до тех пор, пока мы не обработаем все элементы массива.
Псевдокод
function findNGEL(arr) {
const n = arr.length;
const stack = [];
const result = Array(n).fill(-1);
for (let i = 0; i < n; i++) {
while (stack.length > 0 && stack[stack.length - 1] <= arr[i]) {
stack.pop();
}
if (stack.length > 0) {
result[i] = stack[stack.length - 1];
}
stack.push(arr[i]);
}
return result;
}
Давайте теперь рассмотрим реализацию алгоритма в JavaScript.
Реализация кода
function findNGEL(arr) {
const n = arr.length;
const stack = [];
const result = Array(n).fill(-1);
for (let i = 0; i < n; i++) {
while (stack.length > 0 && stack[stack.length - 1] <= arr[i]) {
stack.pop();
}
if (stack.length > 0) {
result[i] = stack[stack.length - 1];
}
stack.push(arr[i]);
}
return result;
}
// Example usage
const arr = [4, 5, 2, 10, 8];
const ngel = findNGEL(arr);
console.log(ngel); // [-1, 4, -1, -1, 10]
Объяснение кода Функция findNGEL принимает на вход массив целых чисел и возвращает массив целых чисел, представляющий ближайший больший элемент слева от каждого элемента во входном массиве. Сначала функция инициализирует длину входного массива, пустой стек и массив целых чисел той же длины, что и входной массив, где каждый элемент инициализируется равным -1.
Затем функция перебирает входной массив, используя цикл for. Для каждого элемента функция проверяет, пуст ли стек и больше ли верхний элемент стека, чем текущий элемент. Если стек не пуст и верхний элемент стека меньше или равен текущему элементу, функция извлекает верхний элемент стека. Этот процесс продолжается до тех пор, пока стек не станет пустым или верхний элемент стека не станет больше текущего элемента.
Когда стек пуст или верхний элемент стека больше текущего элемента, функция проверяет, не пуст ли стек. Если стек не пуст, ближайший больший элемент слева от текущего элемента равен верхнему элементу стека. В противном случае ближайший больший элемент слева от текущего элемента равен -1.
Наконец, функция помещает текущий элемент в стек и продолжает итерацию по входному массиву. Как только все элементы входного массива обработаны, функция возвращает массив ближайших больших элементов слева.
В представленном примере использования функция findNGEL вызывается с массивом целых чисел [4, 5, 2, 10, 8]. Функция возвращает массив целых чисел [-1, 4, -1, -1, 10], который указывает, что ближайший больший элемент слева от первого элемента во входном массиве равен -1, ближайший больший элемент к слева от второго элемента во входном массиве равно 4, ближайший больший элемент слева от третьего элемента во входном массиве равен -1, ближайший больший элемент слева от четвертого элемента во входном массиве равен -1, и ближайший больший элемент слева от пятого элемента во входном массиве равен 10.
Спасибо, что прочитали! Если вам понравилось читать этот пост, вы получили от него помощь, знания, вдохновение и мотивацию и хотите поддержать меня — вы можете Купить мне кофе. Ваша поддержка действительно имеет значение.
Заключение
Задача ближайшего большего элемента слева (NGEL) — это классическая алгоритмическая задача, которую можно решить с помощью структуры данных стека. В этой статье мы подробно обсудили проблему NGEL и представили практическую реализацию алгоритма на JavaScript. Реализация использует стек для отслеживания более крупных элементов, просмотренных до сих пор, и выполняет итерацию по входному массиву, чтобы вычислить ближайший больший элемент слева от каждого элемента. Реализация имеет временную сложность O(n) и пространственную сложность O(n), где n — длина входного массива.
