![Для последовательности A = [a1, a2, …, an] для каждого индекса i найти такой индекс j такой, что 1) j < i; 2) i - j стремится к минимуму; 3) a[j] < a[i]](/public/images/library/external/library-detail-hero-book.png)
Условие:
Для последовательности A = [a1, a2, …, an] для каждого индекса i найти такой индекс j такой, что 1) j < i; 2) i - j стремится к минимуму; 3) a[j] < a[i]
Решение:
Рассмотрим задачу: для каждого элемента последовательности A = [a1, a2, …, an] необходимо найти такой индекс j, что выполняются следующие условия:
- j < i, то есть искомый элемент находится слева от текущего;
- расстояние i - j минимально – то есть из всех элементов слева выбирается ближайший к i;
- a[j] < a[i] – значение на найденном индексе меньше, чем значение на текущем индексе i.
Чтобы решить эту задачу эффективно (за линейное время O(n)), можно использовать идею, аналогичную задаче «ищем предыдущий меньший элемент», применив стек. Далее приведём...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи