85. Maximal Rectangle

leetcode hard

#array#csharp#dynamic-programming#hard#leetcode#math#matrix#string

Task

Дана бинарная матрица размером 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.

C# solution

matched/original

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix.Length == 0)
            return 0;
        int maxarea = 0;
        int[][] dp = new int [matrix.Length][];
        for (int a = 0; a < dp.Length; a++) dp[a] = new int[matrix[0].Length];
        for (int i = 0; i < matrix.Length; i++) {
            for (int j = 0; j < matrix[0].Length; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
                    int width = dp[i][j];
                    for (int k = i; k >= 0; k--) {
                        width = Math.Min(width, dp[k][j]);
                        maxarea = Math.Max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaximalRectangle(char[][] matrix) {
        if (matrix.size() == 0)
            return 0;
        int maxarea = 0;
        int[][] dp = new int [matrix.size()][];
        for (int a = 0; a < dp.size(); a++) dp[a] = new int[matrix[0].size()];
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
                    int width = dp[i][j];
                    for (int k = i; k >= 0; k--) {
                        width = min(width, dp[k][j]);
                        maxarea = max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
}

Java solution

matched/original

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int maxarea = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;

                    int width = dp[i][j];

                    for (int k = i; k >= 0; k--) {
                        width = Math.min(width, dp[k][j]);
                        maxarea = Math.max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
}

JavaScript solution

matched/original

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;
};

Python solution

matched/original

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        maxarea = 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "0":
                    continue
                width = dp[i][j] = dp[i][j - 1] + 1 if j else 1
                for k in range(i, -1, -1):
                    width = min(width, dp[k][j])
                    maxarea = max(maxarea, width * (i - k + 1))
        return maxarea

Go solution

matched/original

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    maxarea := 0
    dp := make([][]int, len(matrix))
    for i := range dp {
        dp[i] = make([]int, len(matrix[0]))
    }
    for i := 0; i < len(matrix); i++ {
        for j := 0; j < len(matrix[0]); j++ {
            if matrix[i][j] == '1' {
                dp[i][j] = 1
                if j != 0 {
                    dp[i][j] += dp[i][j-1]
                }
                width := dp[i][j]
                for k := i; k >= 0; k-- {
                    width = min(width, dp[k][j])
                    maxarea = max(maxarea, width*(i-k+1))
                }
            }
        }
    }
    return maxarea
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

Explanation

Algorithm

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️⃣

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

😎