Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCode53 статьи, давайте посмотрим на 85 вопросов в LeetCode, Максимальный прямоугольник (прямоугольник максимальной площади).
Сегодняшняя тема чем-то похожа на вопрос «Самый большой прямоугольник в гистограмме» из предыдущей статьи, поэтому, если вы не читали предыдущую статью, рекомендуем сначала посмотреть предыдущую.
LeetCode 84 | Монотонный стек для решения задачи максимального прямоугольника
Официальная сложность 85 вопросов:Hard, 2757 лайков, 69 отклонений, а проходной балл составляет около 37,2%. Его ситуация очень похожа на 84 вопроса, коэффициент лайков очень высокий, а затем аналогичный процент прохождения. Хотя это вариант из 84 вопросов, общее качество вопросов по-прежнему очень высокое, и за это его не критиковали. Итак, по сравнению с 84 вопросами, какие в нем изменения, давайте посмотрим на вопросы вместе.
смысл названия
Учитывая числовую матрицу, содержащую только 0 и 1, найдите прямоугольник с наибольшей площадью, состоящей из 1 в этой матрице, и верните площадь.
Давайте посмотрим на пример:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
Ответ 6, который представляет собой прямоугольник, заключенный в эту часть 1:
отвечать
Все еще старые правила, мы начинаем сСамый простой способНачните, и выведите лучшие идеи немного.
Насилие
Прежде всего, конечно же, насилие, ищем прямоугольник.Нахождение прямоугольника напрямую немного громоздко. В отличие от человеческого глаза, компьютерные программы могут напрямую получать информацию, связанную с графикой, но компьютеры не могут и могут получать информацию только об одном месте. Таким образом, для нас нереально позволить программе напрямую судить о прямоугольнике, но мы можем зафиксировать прямоугольник с помощью характерных точек, что также является обычной процедурой в отрасли.
Обычно есть два способа заблокировать прямоугольник, первыйОпределяется центральной точкой, длиной и шириной прямоугольника.. Этот часто используется в различных алгоритмах распознавания изображений и обнаружения целей.Результатами предсказания модели являются координаты центральной точки изображения и длины длины и ширины.
Второй способ можетОпределяется двумя точками на диагонали прямоугольника, этот метод работает только для прямоугольников, параллельных осям координат. Например, на рисунке ниже, независимо от того, знаем ли мы (x2, y2), (x3, y3) или (x1, y1), (x4, y4), мы можем определить прямоугольник.
После того, как у нас есть метод определения прямоугольника, нам просто решить его методом грубой силы. Мы используем эти значения для перечисления всех возможных прямоугольников, а затем по очереди обходим каждый элемент в прямоугольнике, чтобы определить, все ли они 1, если нет, то исключаем, иначе используем для обновления ответа.
Этот метод осуществим, но для оценки он должен быть почти
Масштабы для нас явно неприемлемы.
анализировать проблему
В решении грубой силы мы сталкиваемся с трудностью временной сложности.Если мы хотим оптимизировать, мы должны решить проблему сложности.Как решить проблему сложности? Думать определенно недостаточно, нам нужно изменить свое мышление и найти прорыв.
Шкала сложности нашего перечисления настолько высока, потому что мыпрошли все прямоугольники, обход самого прямоугольника — очень дорогой шаг по временной сложности. Если я не хочу пересекать прямоугольник, есть ли другой способ получить максимальную площадь? Если задуматься над предыдущим вопросом, то легко получить ответ.
Среди 84 вопросов в предыдущем вопросе вопрос дает вертикальный тип прямоугольников, и требуется максимальная площадь, которую можно найти в комбинации этих прямоугольников.
В этом вопросе мы можемПроделайте аналогичное преобразование с цифровой матрицей 01., количество единиц, непрерывно идущих снизу, рассматривается как высота вертикально расположенного прямоугольника, так что мы можем использовать идею предыдущего вопроса для решения этой проблемы.
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
Например, приведенную выше матрицу можно преобразовать в [4, 0, 0, 3, 0], фактически мы смотрим ее столбец за столбцом,Количество последовательных единиц от самой низкой точки вверх. Однако максимальная площадь, найденная таким образом, равна 4, а не 6. Причина в том, что, поскольку нижний слой, который мы ищем, неверен, это не обязательно самая большая площадь, полученная, если взять последнюю строку в качестве нижней. поверхность. Итак, нам нужно пройти строку, которая является нижним слоем, а затем использовать этот метод, чтобы найти наибольшую область, и самая большая область, найденная в глобальном масштабе, является ответом.
В предыдущем вопросе, когда мы вычисляли площадь прямоугольника, мы использовали два монотонных стека для вычисления самого дальнего расстояния, на которое может простираться определенная высота влево и вправо, На самом деле это не обязательно. из-за СШАС помощью стека также можно вычислить границы обеих сторон одновременно.. Например: [1, 3, 6, 7], текущий элемент равен 5. Нам нужно нажать 6, 7 и нажать 5. Мы знаем, что левая граница числа 5 равна 3, но подумайте об этом, для числа 7 мы знаем его левую и правую границы. Левая граница числа 7 равна 6, а правая граница равна 5. Другими словами, для элемента наверху стека его левая граница — это stack[top-1], его правая граница — это текущая позиция i, а его ширина равна i — stack[top-1] — 1.
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
# 求出行数n和列数m
n = len(matrix)
if n == 0:
return 0
m = len(matrix[0])
# 存储每一层的高度
height = [0 for _ in range(m+1)]
res = 0
# 遍历以哪一层作为底层
for i in range(n):
sk = [-1]
for j in range(m+1):
# 计算j位置的高度，如果遇到0则置为0，否则递增
h = 0 if j == m or matrix[i][j] == '0' else height[j] + 1
height[j] = h
# 单调栈维护长度
while len(sk) > 1 and h < height[sk[-1]]:
res = max(res, (j-sk[-2]-1) * height[sk[-1]])
sk.pop()
sk.append(j)
return res
Суммировать
На первый взгляд этот вопрос кажется очень сложным, но после того, как мы его проанализируем и деформируем, он сноваВернулась к обычной проблеме монотонного стека.. В использовании монотонных стеков есть две детали, одна из которых заключается в том, что стек находится в-1 был вставлен во время инициализации, вставка -1 используется как пейссеттер, то есть крайняя левая граница, до которой можно добраться во всех случаях. Еще одна деталь0 был вставлен в конце обслуживания, цель вставки 0 состоит в том, чтобы выталкивать все элементы в стеке, потому что только элементы, извлеченные из стека, будут вычислять сформированную область, что может гарантировать, что ни одна ситуация не будет упущена.
Помимо вышеперечисленного есть и другие детали, такие как длина создаваемого массива и формула вычисления площади прямоугольника. Во многих случаях причина сложности реализации алгоритма заключается именно в том, что необходимо учитывать множество деталей, а общая логика не очень ясна, что требует от нас много размышлений. В целом, это очень хороший вопрос, который заслуживает тщательного изучения.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
В этой статье используетсяmdniceнабор текста