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