一【題目類(lèi)別】

• 矩陣

二【題目難度】

• 困難

三【題目編號(hào)】

• 85.最大矩形

四【題目描述】

• 給定一個(gè)僅包含 0 和 1 、大小為 rows x cols 的二維二進(jìn)制矩陣，找出只包含 1 的最大矩形，并返回其面積。

五【題目示例】

• 示例 1：

  • 
  • 輸入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
  • 輸出：6
  • 解釋?zhuān)鹤畲缶匦稳缟蠄D所示。

• 示例 2：

  • 輸入：matrix = []
  • 輸出：0

• 示例 3：

  • 輸入：matrix = [[“0”]]
  • 輸出：0

• 示例 4：

  • 輸入：matrix = [[“1”]]
  • 輸出：1

• 示例 5：

  • 輸入：matrix = [[“0”,“0”]]
  • 輸出：0

六【題目提示】

• $rows==matrix.length$
• $cols==matrix[0].length$
• $1<=row,cols<=200$
• $matrix[i][j]{為}^{\prime }{0}^{\prime }{或}^{\prime }{1}^{\prime }$

七【解題思路】

• 首先創(chuàng)建一個(gè)輔助數(shù)組left，用于記錄每個(gè)位置的左邊連續(xù) ‘1’ 的個(gè)數(shù)
• 然后對(duì)于二維數(shù)組中每一個(gè)點(diǎn)，我們計(jì)算以這個(gè)點(diǎn)作為右下角的矩形的面積，我們利用“向上拓展”的方式，矩陣的寬度是“向上拓展”的過(guò)程中最短的寬度，高度通過(guò)當(dāng)前位置減去遍歷到的位置然后加一得到（因?yàn)閿?shù)組從零開(kāi)始計(jì)數(shù)）
• 然后通過(guò)比較最大值得到最大矩形的面積
• 最后返回結(jié)果即可

八【時(shí)間頻度】

• 時(shí)間復(fù)雜度：$O(m^{2}n)$，$m、n$分別為傳入的二維數(shù)組的行數(shù)和列數(shù)
• 空間復(fù)雜度：$O(mn)$，$m、n$分別為傳入的二維數(shù)組的行數(shù)和列數(shù)

九【代碼實(shí)現(xiàn)】

1. Java語(yǔ)言版

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] left = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == '1'){
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }
        int res = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == '0'){
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for(int k = i - 1;k >= 0;k--){
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area,(i - k + 1) * width);
                }
                res = Math.max(res, area);
            }
        }
        return res;
    }
}

2. C語(yǔ)言版

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize)
{
    int m = matrixSize;
    int n = matrixColSize[0];
    int** left = (int **)malloc(sizeof(int*) * m);
    for(int i = 0;i < m;i++)
    {
        left[i] = (int*)calloc(n, sizeof(int));
    }
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(matrix[i][j] == '1')
            {
                left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }
    int res = 0;
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(matrix[i][j] == '0')
            {
                continue;
            }
            int width = left[i][j];
            int area = width;
            for(int k = i - 1;k >= 0;k--)
            {
                width = fmin(width, left[k][j]);
                area = fmax(area, (i - k + 1) * width);
            }
            res = fmax(res, area);
        }
    }
    return res;
}

3. Python語(yǔ)言版

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

4. C++語(yǔ)言版

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> left(m, vector<int>(n, 0));
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == '1'){
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }
        int res = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == '0'){
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for(int k = i - 1;k >= 0;k--){
                    width = fmin(width, left[k][j]);
                    area = fmax(area, (i - k + 1) * width);
                }
                res = fmax(res, area);
            }
        }
        return res;
    }
};

十【提交結(jié)果】

1. Java語(yǔ)言版
   

2. C語(yǔ)言版
   

3. Python語(yǔ)言版
   

4. C++語(yǔ)言版
   文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-640750.html

到了這里，關(guān)于【LeetCode每日一題】——85.最大矩形的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！