Как узнать
для каждого элемента ближайший следующий или предыдущий, который больше или меньше: следующий более тёплый день, ближайший столбик выше.
Как решать такие задачи
- Определи, чего ждёт каждый элемент: следующего большего или следующего меньшего.
- Держи в стеке индексы тех, кто ещё ждёт. Индексы, а не значения, чтобы считать расстояния.
- Для каждого нового элемента снимай верх, пока новый его превосходит (больше или меньше — смотря что ищешь). Каждый снятый индекс нашёл ответ.
- Положи новый индекс. У индексов, оставшихся в стеке в конце, ответа нет: дай им значение по умолчанию.
Где встречается
- Выпуклая оболочка. Алгоритм Грэхема, которым GEOS и PostGIS считают ST_ConvexHull, обходит точки по кругу и держит границу оболочки в стеке. Новая точка снимает с верха те, что оказались внутри, так же как в монотонном стеке новый элемент снимает тех, кого он побил.
- Разбор формул. Алгоритм «сортировочная станция» держит операторы в стеке по возрастанию приоритета. Новый оператор сначала снимает с верха всех, кто связывает не слабее его. Так калькуляторы и парсеры формул превращают 2 + 3 × 4 в порядок вычислений.