Самый большой прямоугольник в гистограмме

Дан список неотрицательных целых чисел: высоты столбцов гистограммы, стоящих вплотную друг к другу; ширина каждого столбца равна 1. Найдите площадь самого большого прямоугольника, который целиком помещается внутри гистограммы и опирается на её основание: он занимает несколько подряд идущих столбцов, а его высота не больше самого низкого из них. Для пустого списка верните 0.

В списке до 20 000 столбцов, высота каждого от 0 до 20 000. Решение за O(n²) на самом большом тесте не уложится во время.

Пример: [3, 1, 4, 4, 2] → 8 (два столбца высоты 4).

Источник: задача CodeShare