Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCodeВ 52-й статье давайте рассмотрим 84-й вопрос LeetCode, Самый большой прямоугольник в гистограмме (максимальная прямоугольная площадь).
Официальная сложность этого вопроса — Hard, с 3581 отметкой «Нравится» и 80 отклонениями, с процентом прохождения около 34,7%. Судя по проценту ответов, сложность на самом деле неплохая, не особенно большая, но высокий коэффициент похвалы за этот вопрос показывает, что качество вопроса очень хорошее. На самом деле это такочень классический, что лично я настоятельно рекомендую. Рекомендуется, чтобы каждый, у кого есть способности, ответил на этот вопрос, и это будет очень полезно.
смысл названия
Допустим, у нас есть рядПрямоугольники с одинаковой шириной, равной 1, располагаются вертикально вместе., Какова площадь наибольшего прямоугольника, который может быть заключен в этот узор?
Например, на изображении выше у нас есть 6 прямоугольников, ширина каждого из которых равна 1. Самый большой прямоугольник, который мы можем найти, должен быть прямоугольником, окруженным цифрами 5 и 6 посередине:
Задаче задано число, содержащее несколько целых чисел, представляющих собой высоту этих прямоугольников, и требуется вернуть площадь прямоугольника с наибольшей площадью, которую можно найти.
Образец
Input: [2,1,5,6,2,3]
Output: 10
Найдите максимальное значение в интервале
Когда вы это поймете, вы сможете почувствовать сложность этого вопроса: у нас действительно не было хороших идей, когда мы пришли, и тема была относительно ясна, и не так много отправных точек для анализа. Поэтому мы можем сначала подумать о самом простом решении.
Самое простое решениеНайдите все прямоугольники, которые можно вложить, затем сравните площади между ними и найдите наибольшую из них. Мы можем легко думать о пересечении начальной позиции прямоугольника, поэтому мы получаем ширину прямоугольника. Что касается длины прямоугольника, то она тоже очень проста, т.е.Самая низкая высота в выбранном сегменте.
Мы можем сделать небольшое преобразование мышления Предполагая, что все эти прямоугольники представляют собой деревянные планки, мы хотим выбрать деревянные планки, чтобы сделать деревянные бочки. Тогда согласноЭффект бочки, высота воды, заключенной в бочку, определяется кратчайшим деревянным бруском, а высота площади, заключенной тем же прямоугольником, определяется кратчайшим из этих прямоугольников. То есть после того, как мы определили интервал, нам нужно только найти наименьшее число в интервале. Таким образом, этот вопрос становитсяЗадача нахождения максимального значения интервала, например, на изображении выше, если мы выберем последние три прямоугольника, то его высота будет равна 2.
Мы предполагаем, что есть всего n длинных прямоугольников на выбор, тогда комбинации головы и хвоста, которые мы можем выбрать, равны
, что является примерно интервалом порядка квадрата n. Для каждого интервала нам нужно пройти элементы в них, чтобы получить минимальное значение, для чего требуется
время прохождения, поэтому общая сложность должна быть
величина. Очевидно, что это очень большой порядок, и трудно вычислить решение, когда n превышает 1000.
Эта идея явно недостаточно хороша, и нам нелегко ее оптимизировать. Например, если вы изучили структуры данных, такие как деревья отрезков, вы также можете подумать об использовании деревьев отрезков.Мы можем оптимизировать каждый запрос, чтобы найти минимальное значение для
, но и тогда конечная сложность высока. Это потому, что мы тратим время на пересечение начала и конца интервала.
, который трудно оптимизировать. такПредел этой идеи определен, и мы не можем делать серьезные оптимизации..
С этого момента, если есть лучшее решение, его нельзя делать таким образом.
Обратное мышление
Хотя приведенная выше идея неосуществима, она дает положительную идею. Перебираем все интервалы, а затем через деревянные планки в интервале определяем высоту прямоугольника, охваченного площадью, после чего получаем площадь прямоугольника.
Поскольку эта дорога не работает, можем ли мыобратное мышлениеШерстяная ткань? Предположим, что мы нашли ответ, который представляет собой прямоугольник, заключенный в деревянные бруски отрезка [a, b], и его высота равна h. Тогда по эффекту бочкиОдна из деревянных планок на участке от а до б должна иметь длину h. Например, если [5, 6, 2, 3] на рисунке ниже нужно заключить в прямоугольник, высота может быть только 2.
В таком случае мы можемНайдите самый большой прямоугольник, который можно составить из деревянной планки в качестве короткой доски.. Например, на картинке выше, если мы ищем первую деревянную полоску, мы можем найти только ее саму, поэтому площадь этого прямоугольника равна 1 х 2 = 2. Если вы ищете вторую деревянную полосу как короткую доску, вы можете найти весь интервал, и его соответствующая площадь будет 1 x 6 = 6.
Поскольку у нас есть только n деревянных полосок, и каждая деревянная полоска используется как короткая доска для нахождения самого большого прямоугольника, мы должны быть в состоянии найти не более n прямоугольников.Окончательный ответ должен быть в этих n прямоугольниках, в позитивном мышлении нам нужно найти интервал деревянных планок
Сложность, однако, мы ищем короткую доску, только нужно
, то есть пространство поиска этой идеи меньше, и пока мы обеспечиваем эффективность поиска, мы можем найти ответ быстрее.
Чтобы найти самый большой прямоугольник, соответствующий каждой деревянной полосе, нам нужно найти самое дальнее положение, на которое каждая короткая доска может простираться влево и вправо. Например, в приведенном выше примере мы можем получить [0, 5, 3, 3, 5, 5] в соответствии с самой дальней позицией каждой деревянной полосы, идущей вправо.Аналогично мы можем получить массив каждой деревянной полосы, простирающейся влево: [0, 0, 2, 3, 2, 5]. Когда у нас есть эти два массива, мы можемВычислите площадь наибольшего прямоугольника с каждой деревянной полосой в качестве короткой доски., тот, у которого наибольшая площадь, является ответом.
Здесь мы можем использоватьМонотонный стекПриходите спросить, мы используем упорядоченный стек для сохранения позиции расширения. Например, мы используем монотонную стопку, которая увеличивается от нижней части стопки к вершине стопки, чтобы сохранить положение, при котором каждая деревянная планка простирается вправо. Когда мы сталкиваемся с новым баром, все значения длиннее его выталкиваются из стека. Для этих значений новая полоса является ее правой границей. Например, [5, 6, 2], прочитайте 5 в начале и поместите его в стек. Затем прочитайте 6, потому что 6 больше, чем 5 на вершине стека, поэтому 6 помещается в стек. Наконец, считывается 2. Поскольку 2 меньше 6, из стека выталкивается 6. Для 6 позиция 2 является его правой границей. Именно потому, что 2 меньше его, его нужно вытолкнуть, что также означает, что элементы слева от 2 больше, чем 6, в противном случае 6 нужно вытолкнуть из стека раньше. Точно так же 2 также является правой границей 5.
Если вы не понимаете монотонные стеки, вы можете обратиться к предыдущей статье:
Мы переворачиваем приведенную выше логику, чтобы получить логику решения левой границы. После того, как у нас есть левая и правая границы, нам нужно всего лишь умножить длину интервала между ними, чтобы получить площадь прямоугольника.
Далее напишем код:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
# 左侧边界初始化为0
left_side = [0 for i in range(n)]
# 右侧边界初始化为n-1
right_side = [n-1 for _ in range(n)]
stack_left = []
stack_right = []
for i in range(n):
h = heights[i]
# 弹出栈中所有比当前元素小的值
# 注意，栈内存储的是下标
while len(stack_right) > 0 and h < heights[stack_right[-1]]:
tail = stack_right[-1]
stack_right.pop()
right_side[tail] = i - 1
# 当前元素入栈
stack_right.append(i)
# 把坐标翻转，等价于逆向遍历
i_ = n - 1 - i
h = heights[i_]
# 维护单调栈的逻辑同上
while len(stack_left) > 0 and h < heights[stack_left[-1]]:
tail = stack_left[-1]
stack_left.pop()
left_side[tail] = i_ + 1
# 当前元素入栈
stack_left.append(i_)
ret = 0
for i in range(n):
# 矩形面积等于右侧边界-左侧边界+1 x 高度
cur = (right_side[i] - left_side[i] + 1) * heights[i]
ret = max(ret, cur)
return ret
Суммировать
Если вы хотите решить эту проблему, бесполезно просто понимать смысл проблемы и разбираться в монотонном стеке.Необходимо понять смысл, оптимальный метод выводится из простейшего решения,Также необходимо глубоко понимать структуру данных монотонного стека., может применяться гибко.
Кроме того, вам нужно уделять особое внимание граничным случаям в вашем коде. Например, необходимо учитывать установку левой и правой границ во время инициализации и возможность последовательных равных элементов. Хотя код выглядит просто, он скрывает множество деталей, поэтому просто смотреть на код бесполезно, лучше реализовать его самостоятельно.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
В этой статье используетсяmdniceнабор текста