Как бы загадочно это ни звучало, это проблема в практических задачах Hacker-earth по критериям структуры данных. Формулировка проблемы приведена ниже:

В задаче задан массив A, содержащий N целых чисел, для каждого i (1≤i≤N) найдите x + y, где x - наибольшее число меньше i такое, что A [x] ›A [i] и y - наименьшее число больше i такое, что A [y] ›A [i]. Если не существует x ‹i такого, что A [x]› A [i], то возьмем x = −1. Аналогично, если не существует y ›i такого, что A [y]› A [i], то возьмем y = −1.

Формат ввода:
Первая строка состоит из единственного целого числа, обозначающего N.
Вторая строка состоит из N целых чисел, разделенных пробелами, обозначающих массив A .

Формат вывода:
Печать N целых чисел, разделенных пробелами, обозначающих x + y для каждого i (1≤i≤N)

Ограничения:
1≤N≤10⁶
1≤A [i] ≤10¹⁸

Эта проблема была задана vaibhab jamini и была протестирована prateek garg. Он также появился на хакерской задаче под названием codemonk с некоторыми другими проблемами, связанными со структурой данных.

Обсуждение:

Итак, прежде всего, у кого-то в голове появится очень простой алгоритм, который заключается в том, что анализирует массив и для каждого элемента массива находит x и y, а затем все готово. Найти таким образом координаты x и y очень просто. Но как только вы это напишете, вы поймете, что этот алгоритм представляет собой алгоритм порядка O (n²), и поэтому он даст вам ограничение по времени, когда ограничение достигает 10⁶.

Такое тоже бывает. При написании следующего кода C я решил 3 случая, и другие входные данные содержат уведомление «превышено время». Это означает, что вам нужен лучший алгоритм.

Здесь я упоминаю свой наивный метод рефералов.

#include ‹stdio.h›
int main ()
{int N; int i; int j;
scanf («% d», & N);
long long * A = (long long *) calloc (N + 2, sizeof (long long));
long long * B = (long long *) calloc (N + 2, sizeof (long long));
for (i = 0; i ‹N; i ++)
{
scanf («% lld ”, & A [i]);
}
for (i = 0; i‹ N; i ++)
{
int x = -1; int y = -1;
for (j = i-1; j ›-1; j -)
{
if (A [j]› A [i])
{
x = j + 1;
break;
}
}
for (j = i + 1; j ‹N; j ++)
{
if (A [j] ›A [i])
{
y = j + 1;
break;
}
}
B [i] = x
B [i + 1] = i;
B [i + 2] = y;
printf («% d», B [i]) ;
}

}

Теперь я начинаю искать лучший алгоритм. Теперь, как кажется, это вариационная проблема так называемой «проблемы диапазона запасов», в которой каждому дается массив дневных цен акций по номиналу и предполагается, что он должен найти количество дней, в течение которых цена акции была меньше, чем в тот день. цена. Этот вопрос решается с помощью реализации стека.

Сначала нужно я. Затем находят индекс h (i), который обозначает максимальный индекс, меньший, чем i, такой, что A [h (i)] ›A [i]. Затем сохраняют i, h (i), h (h (i)) .. в стеке. Теперь, когда переходят от i к i + 1, тогда

если A [i + 1] ‹A [i], то x = i; else A [i + 1] ›A [i], поэтому стек может напрямую предоставить следующее лучшее решение для этого, поскольку предыдущий элемент, больший, чем A [i], является предыдущим элементом в стеке. Итак, в основном мы делаем следующее:

(а) создаем ложу справа i = 0. Сохраняем h (0).

(b) На каждом шаге i мы сравниваем верх стека и A [i]. Выскакиваем до вершины ›A [i]. Затем нажимаем i. Если стек становится пустым, мы нажимаем i в качестве первого узла, и требуемый x для i становится -1.

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

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