Я являюсь автором Максимального прямоугольного решения на LeetCode, на котором основан этот ответ.
Поскольку решение на основе стека уже обсуждалось в других ответах, я хотел бы представить оптимальное O(NM) решение для динамического программирования, исходящее от пользователя morrischen2008 .
Интуиция
Представьте себе алгоритм, в котором для каждой точки мы вычислили прямоугольник, выполнив следующее:
Нахождение максимальной высоты прямоугольника путем итерации вверх до достижения заполненной области
Нахождение максимальной ширины прямоугольника путем итерации влево и вправо до высоты, не соответствующей максимальной высоте прямоугольника
Например, найти прямоугольник, определенный желтой точкой:
Мы знаем, что максимальный прямоугольник должен быть одним из прямоугольников, построенных таким образом (максимальный прямоугольник должен иметь точку на своем основании, где следующий заполненный квадрат находится на высоте над этой точкой).
Для каждой точки мы определяем некоторые переменные:
h - высота прямоугольника, определяемая этой точкой
l - левая граница прямоугольника, определяемая этой точкой
r - правая граница прямоугольника, определяемая этой точкой
Эти три переменные однозначно определяют прямоугольник в этой точке. Мы можем вычислить площадь этого прямоугольника с помощью h * (r - l). Глобальный максимум всех этих областей - наш результат.
Используя динамическое программирование, мы можем использовать h, l и r каждой точки в предыдущей строке, чтобы вычислить h, l и r для каждой точки в следующий ряд по линейному времени.
Алгоритм
Для данной строки matrix[i] мы отслеживаем h, l и r каждой точки в строке, определяя три массива - height, left и right.
height[j] будет соответствовать высоте matrix[i][j] и т. Д. И т. Д. С другими массивами.
Теперь возникает вопрос, как обновить каждый массив.
height
h определяется как количество непрерывных незаполненных пробелов в линии от нашей точки. Мы увеличиваем, если есть новый пробел, и устанавливаем его в ноль, если пробел заполнен (мы используем '1', чтобы указать пустой пробел, и '0' как заполненный).
new_height[j] = old_height[j] + 1 if row[j] == '1' else 0
left
Рассмотрим, что вызывает изменения левой границы нашего прямоугольника. Поскольку все экземпляры заполненных пробелов, встречающиеся в строке выше текущей, уже включены в текущую версию left, единственное, что влияет на нашу left, - это если мы встречаем заполненную пробел в нашей текущей строке.
В результате мы можем определить:
new_left[j] = max(old_left[j], cur_left)
cur_left - это больше, чем крайнее правое заполненное пространство, с которым мы столкнулись Когда мы «расширяем» прямоугольник влево, мы знаем, что он не может расширяться после этой точки, иначе он попадет в заполненное пространство.
right:
Здесь мы можем повторно использовать наши рассуждения в left и определить:
new_right[j] = min(old_right[j], cur_right)
cur_right - самое левое вхождение заполненного пространства, с которым мы столкнулись.
Осуществление
def maximalRectangle(matrix):
if not matrix: return 0
m = len(matrix)
n = len(matrix[0])
left = [0] * n # initialize left as the leftmost boundary possible
right = [n] * n # initialize right as the rightmost boundary possible
height = [0] * n
maxarea = 0
for i in range(m):
cur_left, cur_right = 0, n
# update height
for j in range(n):
if matrix[i][j] == '1': height[j] += 1
else: height[j] = 0
# update left
for j in range(n):
if matrix[i][j] == '1': left[j] = max(left[j], cur_left)
else:
left[j] = 0
cur_left = j + 1
# update right
for j in range(n-1, -1, -1):
if matrix[i][j] == '1': right[j] = min(right[j], cur_right)
else:
right[j] = n
cur_right = j
# update the area
for j in range(n):
maxarea = max(maxarea, height[j] * (right[j] - left[j]))
return maxarea