Почему это работает
- Самый большой прямоугольник высотой с самый низкий столбик под ним и может тянуться от этого столбика до первого более низкого с каждой стороны. Поэтому достаточно измерить каждый столбик один раз на всю эту ширину.
- Столбик снимает первый более низкий справа, на i. Под ним в стеке — первый более низкий слева: те, что между, были выше и уже сняты. Поэтому он тянется от left до i − 1.
- Лишний шаг с высотой 0 ниже любого столбика, поэтому в конце ни один не останется неизмеренным.
Сложность
Время O(n): каждый столбик кладётся один раз и снимается один раз, а каждое снятие меряется за O(1). Память O(n) на стек.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗