Задача: 85. Maximal Rectangle
Сложность: hard

Дана бинарная матрица размером rows x cols, заполненная 0 и 1. Найдите наибольший прямоугольник, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

👨‍💻 Алгоритм:

1️⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'.

2️⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea).

3️⃣Применение алгоритма для каждой точки ввода для глобального максимума: Преобразуя входные данные в набор гистограмм, где каждый столбец является новой гистограммой, мы вычисляем максимальную площадь для каждой гистограммы.

😎 Решение:

var maximalRectangle = function (matrix) {
    if (matrix.length === 0) return 0;
    let maxarea = 0;
    let dp = Array(matrix.length)
        .fill(0)
        .map(() => Array(matrix[0].length).fill(0));
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === "1") {
                dp[i][j] = j === 0 ? 1 : dp[i][j - 1] + 1;
                let width = dp[i][j];
                for (let k = i; k >= 0; k--) {
                    width = Math.min(width, dp[k][j]);
                    maxarea = Math.max(maxarea, width * (i - k + 1));
                }
            }
        }
    }
    return maxarea;
};

Ставь 👍 и забирай 📚 Базу знаний