Задача на линейные структуры данных и алгоритмы

[Nikita432472]

Дана последовательность $N$ прямоугольников различной ширины и высоты $(w_{i},h_{i})$. Прямоугольники расположены, начиная с точки $(0, 0)$, на оси $Оx$ вплотную друг за другом (вправо). Требуется найти $M$ - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

[Dmitriy40]

А что в ней олимпиадного? Можно же втупую двойным циклом вычислить:

$$M=\max\left(\min(h_{i\ldots j})\cdot\sum\limits_{k=i}^j w_k \right), \;\forall i,j: 1\le i \le j \le N$$

Ну да, $O(N^2)$, ну и что, ведь не ограничивалось же.

[venco]

Почему $O(N^2)$?
Тело цикла можно легко сделать $O(1)$.

[Dmitriy40]

venco в сообщении #1332954 писал(а):

Тело цикла можно легко сделать $O(1)$.

Только при дополнительном условии $i=1$, т.е. результат должен начинаться в крайней левой точке, тогда да, достаточно пройти правым краем по множеству. Но этого в условии не оговорено. При произвольном же положении левого края результата нужен второй цикл или хитрые эвристики расширения текущего прямоугольника, что совсем не факт что будут быстрее (и вообще найдут глобальный максимум).
Пример: $S_{1..3}=3, S_{5..8}=5, S_{7..9}=4$ - как при таких площадях найти $S_{5..8}$ одним циклом?

-- 16.08.2018, 18:35 --

Даже не так, можно попытаться (примерно за $O(N)$) тянуть за собой и левую границу пока площадь от сдвига правой границы растёт, но на это тоже будет контрпример типа трёх массивов высоких блоков с очень низкими между ними, причём средний максимальный по площади. Низкие блоки не дадут перескочить анализу в среднюю часть и увидеть там максимальную площадь.

[venco]

Да, это я пропустил.
Но $O(N\ln N)$, я думаю, можно получить.

[Dmitriy40]

Нет, все контрпримеры плохи. Я пытался сказать что может быть ситуация, когда в матрице площадей NxN глобальный максимум со всех 4-х сторон окружён глубокими провалами с малой площадью и к нему не существует непрерывного пути неуменьшения площади от любой из 4-х границ. И соответственно одного цикла не хватит. Ну как-то так: высоты (10,10,1,15,10,15,1,15,5) при равной 1 ширине всех, тут решение выделено жирным.

venco в сообщении #1332962 писал(а):

Но $O(N\ln N)$, я думаю, можно получить.

Да, это вероятно можно, где-то в книгах сборников алгоритмов даже описывалось как именно (типа строить дерево/лес иерархии площадей за те самые $O(N\ln N)$, потом просто взять его (максимальный) корень).
Но ведь вопрос оптимальности в условии тоже не стоял.

[mihaild]

Идем слева направа, храня последовательность (самый низкий прямоугольник слева, самый низкий из тех что правее чем он, ...). Каждый прямоугольник максимум один раз в нее добавляется и максимум один раз удаляется, поэтому проход за линейное время. В итоге для каждого прямоугольника запоминаем, где самый правый прямоугольник слева от него с высотой меньше чем у данного. Аналогично идем справа налево.
В итоге для каждого прямоугольника считаем его высоту, умноженную на расстояния до найденных прямоугольников - это площадь, которую можно получить, если упираться в его верхнюю границу.

[Dmitriy40]

mihaild в сообщении #1332967 писал(а):

поэтому проход за линейное время.

Это при стоимости операций с последовательностью $O(1)$, а они точно будут таковы? Не уверен, мне больше верится в $O(\ln N)$, т.к. это сильно похоже на добавление/удаление произвольных элементов сортированного массива/дерева/кучи, для которых обе операции кажется не могут быть одновременно $O(1)$. Так что количество операций да, линейно $O(N)$, но вот сами операции не $O(1)$, а $O(\ln N)$, и в итоге те же $O(N \ln N)$.
Или я что-то недопонял про построение последовательности.

[mihaild]

Dmitriy40 в сообщении #1332979 писал(а):

Это при стоимости операций с последовательностью $O(1)$, а они точно будут таковы?

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

[Dmitriy40]

Ага, со стеком теперь понял. Здорово, да, получается $O(N)$.