最大矩形__牛客网

Java

pein531

单调栈（算法流程）

先做一个预处理，计算每个位置包括自己在内，往右有多少个连续的1。这样矩阵的每一列就都处理成了一个直方图。然后我们对矩阵的每一列都利用单调栈求一遍直方图内求最大矩形面积，从中选出最大的面积就可以了。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 计算每个位置包括自己在内，右边有多少个连续的1
        for(int i = 0; i < n; i++){
            for(int j = m - 2; j >= 0; j--){
                matrix[i][j] = matrix[i][j] == 1? matrix[i][j] + matrix[i][j + 1]: 0;
            }
        }
        int maxArea = 0;
        int j = 0;
        while(j < m){
            int maxHeight = 0;
            int[] heights = new int[n];
            for(int k = 0; k < n; k++){
                heights[k] = matrix[k][j];
                maxHeight = Math.max(maxHeight, heights[k]);
            }
            if(maxHeight == 0) {
                j++;
                continue;
            }
            // 来一遍直方图内的最大矩形
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
            j++;
        }
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, n = heights.length;
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                int h = heights[stack.pop()];
                int L = stack.isEmpty()? 0: stack.peek() + 1;
                maxArea = Math.max(maxArea, h*(i - L));
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int h = heights[stack.pop()];
            int L = stack.isEmpty()? 0: stack.peek() + 1;
            maxArea = Math.max(maxArea, h*(n - L));
        }
        return maxArea;
    }
}

复杂度分析

预处理的时间复杂度为O(n*m)，随后每一列都走“直方图内求最大矩形（单调栈时间复杂度O(n)）”的算法流程，一共m列，因此整体的时间复杂度仍然为O(n*m)。

发表于 2021-12-23 13:10:22 回复(0)

Java

牛客391767071号

/**

* 最大矩形面积 | 最大全一矩形面积

*

* 算法二：动态规划DP/自底向上【参考/延续：“最大子矩阵/最大矩阵和”】

*

* 核心思路：

* 1.问题转换：

* 全一矩形面积 == 全一矩形中各元素之和 == 全一子矩阵和；

* 最大全一矩形面积 == 最大全一子矩阵和 == 最大全一子矩阵

* 2.再求新问题《最大全一子矩阵 | 最大全一子矩阵和》：

* 算法：类似《最大子矩阵/最大矩阵和》

*

* 【运行结果】：通过全部用例运行时间 115ms 占用内存 15976KB

*

* @param matrix int整型二维数组

* @return int整型

*/

public int maximalRectangle1 (int[][] matrix) {

//仅包含 1 的最大矩形并返回面积 /最大矩形面积 | 最大全一矩形面积

int maxArea = Integer.MIN_VALUE;

//输入数据

//1.数组维度N

// int N = matrix.size();

int N = matrix.length;

int M = matrix[0].length;

//2.二维数组、

int[][] arr = matrix;

// int[][] arr = new int[N][];

int index=0;

//性能优化1：前缀和优化

//前缀和数组：sum[N][N]：输入数据时，预先计算的前缀和；存储各列的前1行、前2行、……前n行前缀和。

int[][] prefixSum = new int[N+1][M];

//int[][] prefixSum = new int[N+1][N];

int index2=1;

int q=N;

while(q-->0){

// //使用String.split()方法：去除字符串中的连续空白并将它们视为分隔符

// //这里，\\s+是一个正则表达式，匹配一个或多个空白字符。

// // //String[] data = (in.nextLine()).split(" ");

// // String[] data = (in.nextLine()).split("\\s+");

// // arr[index++] = Arrays.stream(data).mapToInt(Integer::valueOf).toArray();

// List<Integer> list = matrix.get(index);

// arr[index++] = list.stream().mapToInt(Integer::valueOf).toArray();

index++;

//预先计算的前缀和

for(int j=0;j<M;j++) {

//for(int j=0;j<N;j++) {

prefixSum[index2][j] = prefixSum[index2-1][j] + arr[index-1][j];

}

index2++;

}

// //3.计算：找到最大的非空(大小至少是1 * 1)子矩阵。矩阵的大小定义为矩阵中所有元素的和。

// //输出最大子矩阵的大小。

// //算法一：动态规划DP/自底向上 //【最大子矩阵的大小】

// //【结果】-------【最大子矩阵的大小】

// //int maxSubArrSum = maxSubArrSum1(N, arr);

// int maxSubArrSum = maxSubArrSum1(N, arr, prefixSum); //【最大子矩阵】

//3.计算：【最大全一子矩阵 | 最大全一子矩阵和】：基于【最大子矩阵】实现

//【唯一不同/修改】：【最大全一子矩阵】相对于【最大子矩阵】：新增一个规则：不是全一子矩阵，则和为0。

//算法一：动态规划DP/自底向上

// int maxSubArrSum = maxSubArrSum1(N, arr, prefixSum); //【最大子矩阵】

int maxSubArrSum = maxSubArrSum1(N, M, arr, prefixSum); //【最大全一子矩阵】

//5. 返回结果：最大矩形面积

// System.out.println(maxSubArrSum);

// return maxSubArrSum;

maxArea = maxSubArrSum;

return maxArea;

}

/**

* 【最大全一子矩阵 | 最大全一子矩阵和】：基于【最大子矩阵】实现

* 【唯一不同/修改】：【最大全一子矩阵】相对于【最大子矩阵】：新增一个规则：不是全一子矩阵，则和为0。

*

* 【最大子矩阵的大小】【最大子矩阵】

* 找到最大的非空(大小至少是1 * 1)子矩阵。矩阵的大小定义为矩阵中所有元素的和。

*

* 算法一：动态规划DP/自底向上

* 降维关系：【最大子矩阵】

* f(n) = max{h(0,0),h(0,1),h(0,2),……,h(0,n-1),

* h(1,1),h(1,2),……,h(1,n-1),

* h(2,2),……,h(2,n-1),

* ……h(i,j)……,

* h(n-2,n-2),h(n-2,n-1),

* h(n-1,n-1)}

* 其中：子问题h(i,j)：起点行和终点行分别为i和j时，最大子矩阵的大小。i,j：[0,n-1]，且j>=i。

* f(n)降维后的子问题h(i,j)，是一个一维线性问题，比二维问题容易求解。

*

* 子问题h(i,j)：降维关系/计算规则/状态转移方程：

* 子问题h(i,j)：起点行和终点行分别为i和j时，最大子矩阵的大小。i,j：[0,n-1]，且j>=i。

* 子问题h(i,j)，是一个一维线性问题，比二维问题容易求解。

* 解决思路：

* 将起点行i和终点行j之间的每一列，当作一个整体，每列求和压缩为一个数字（列区间和）；

* 这样：“起点行i和终点行j之间的二维矩阵”就等价于一个“一维数组”，

* 求子问题h(i,j)的最大子矩阵的大小，相当于该“一维数组”上的“最大连续子数组之和/连续子数组最大和”

*

* 降维关系：【最大连续子数组之和/连续子数组最大和】

* h(i,j) = h(i,j,n)

* = max{l(1),l(2),……,l(n)};

* 其中：子问题l(n)：以数组元素a[n-1]为右界的最大连续子数组之和/连续子数组最大和。

* 此处：数组元素a[n-1]：第n列的“列区间和”。

* l(n) = max{l(n-1)+a[n-1], a[n-1]}

*

* 性能优化：“列区间和”可基于“列前缀和”来简单计算得到，如下：

* int tmp=sum[k2][i]-sum[k1-1][i]; //第i列[k1,k2]行之和 //列区间和

* 其中：

* 前缀和数组：sum[N][N]：输入数据时，预先计算的前缀和；存储各列的前1行、前2行、……前n行前缀和。

*

* @return 输出最大子矩阵的大小。

*/

public static int maxSubArrSum1(int N, int M, int[][] arr, int[][] prefixSum) {

// public static int maxSubArrSum1(int N, int[][] arr, int[][] prefixSum) {

//最大子矩阵的大小

int maxSubArrSum = -127*100*101;

//1.定义 dp[N][N]：

//dp[i][j]：子问题h(i,j)：起点行和终点行分别为i和j时，最大子矩阵的大小。i,j：[0,n-1]，且j>=i。

int[][] dp = new int[N][N];

//子问题l(n)：以数组元素a[n-1]为右界的最大连续子数组之和/连续子数组最大和。

//此处：数组元素a[n-1]：第n列的“列区间和”。

int[] dpl = new int[M];

//int[] dpl = new int[N];

//2. 计算 dp;

for(int i=0;i<N;i++){

for(int j=i;j<N;j++){ //因为：j>=i

//21.额外行列初始化；

//无；

//22.特殊处理/边界计算/无法降维子问题计算；

//无

//23.统一降维计算；子问题h(i,j)

//降维关系：如前

//【最大连续子数组之和/连续子数组最大和】 ||基于：“列区间和”数组；

//--------------------------------------------------------------

for(int k=0;k<M;k++){

//for(int k=0;k<N;k++){

//21.额外行列初始化；

//无；

//22.特殊处理/边界计算/无法降维子问题计算；

if(k==0){ //l(1)=a[0]; //此处：数组元素a[n-1]：第n列的“列区间和”。

int temp = prefixSum[j+1][k] - prefixSum[i+1-1][k]; //列区间和

//【唯一不同/修改】------------------------------------------------------

//【唯一不同/修改】：【最大全一子矩阵】相对于【最大子矩阵】：新增一个规则：不是全一子矩阵，则和为0。

//【增加处理】：列区间和 != 面积，则不是全一子矩阵，则和为0。

if(temp != (((j+1)-(i+1-1))*1) ){

dpl[k]=0;

//同步计算：子问题h(i,j)

dp[i][j] = dpl[k];

continue;

}

//【唯一不同/修改】------------------------------------------------------

dpl[k]=temp;

//同步计算：子问题h(i,j)

dp[i][j] = dpl[k];

continue;

}

//23.统一降维计算；子问题l(n)

//降维关系：如前

else{

int temp = prefixSum[j+1][k] - prefixSum[i+1-1][k]; //列区间和

//【唯一不同/修改】------------------------------------------------------

//【唯一不同/修改】：【最大全一子矩阵】相对于【最大子矩阵】：新增一个规则：不是全一子矩阵，则和为0。

//【增加处理】：列区间和 != 面积，则不是全一子矩阵，则和为0。

if(temp != (((j+1)-(i+1-1))*1) ){

dpl[k]=0;

//同步计算：子问题h(i,j)

dp[i][j] = Math.max(dp[i][j], dpl[k]);

continue;

}

//【唯一不同/修改】------------------------------------------------------

dpl[k] = Math.max(dpl[k-1]+temp, temp);

//同步计算：子问题h(i,j)

dp[i][j] = Math.max(dp[i][j], dpl[k]);

}

//--------------------------------------------------------------

//25.同步计算：f(n)

maxSubArrSum = Math.max(maxSubArrSum, dp[i][j]);

}

//3. 返回结果

return maxSubArrSum;

}

发表于 2025-04-09 00:44:02 回复(0)

Java

17c89

import java.util.*;

/**
 * NC237 最大矩形
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        return solution(matrix);
    }

    /**
     * 动态规划 + 单调栈
     *
     * heights[i][j]表示以第i行为底的矩形图的第j列的高度
     *
     *                 { 0                    , matrix[i-1][j-1] == 0
     * heights[i][j] = {
     *                 { heights[i-1][j] + 1  , matrix[i-1][j-1] == 1
     *
     *
     * matrix
     * i\j 1 2 3 4 5
     * 1   1 0 1 0 0
     * 2   1 1 1 1 0
     * 3   1 1 1 1 1
     * 4   1 0 0 1 0
     *
     * heights[i][j]
     * i\j 1 2 3 4 5
     * 1   1 0 1 0 0
     * 2   2 1 2 1 0
     * 3   3 2 3 2 1
     * 4   4 0 0 3 0
     *
     * @param matrix
     * @return
     */
    private int solution(int[][] matrix){
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] heights = new int[n+1][m+1];

        // 以第i行为底的矩形图的第j列的高度
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(matrix[i-1][j-1] == 1){
                    heights[i][j] = heights[i-1][j] + 1;
                }
            }
        }

        Stack<Integer> leftStack;
        Stack<Integer> rightStack;
        HashMap<Integer, Integer> leftMap;
        HashMap<Integer, Integer> rightMap;

        int area = 0;
        // 分别计算以各行为底的矩形图
        for(int i=1; i<=n; i++){
            leftStack = new Stack<>();
            rightStack = new Stack<>();
            leftMap = new HashMap<>();
            rightMap = new HashMap<>();
            int height;
            int index;
            // 单调栈
            for(int j=1; j<=m; j++){
                height = heights[i][j];
                // 单调增 从左往右 查找左边第一个小于当前元素的索引 0-左边界(表示未找到)
                while(!leftStack.isEmpty() && height<=heights[i][leftStack.peek()]){
                    leftStack.pop();
                }
                index = leftStack.isEmpty()?0:leftStack.peek();
                leftMap.put(j, index);
                leftStack.push(j);
            }
            // 单调栈
            for(int j=m; j>0; j--){
                height = heights[i][j];
                // 单调增 从右往左 查找右边第一个小于当前元素的索引 (m+1)-右边界(表示未找到)
                while(!rightStack.isEmpty() && height<=heights[i][rightStack.peek()]){
                    rightStack.pop();
                }
                index = rightStack.isEmpty()?m+1:rightStack.peek();
                rightMap.put(j, index);
                rightStack.push(j);
            }
            
            // 计算当前矩形图 最大矩形面积
            for(int j=1; j<=m; j++){
                area = Math.max(area, heights[i][j]*(rightMap.get(j)-leftMap.get(j)-1));
            }
        }

        return area;
    }
}

发表于 2025-02-13 13:39:52 回复(0)

Java

牛客499848474号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        // write code here
        if (matrix.length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];

        for (int i = 0; i < cols; i++) {
            for (int j = 0; j < rows; j++) {
                // dp[j][i]
                if (j == 0) {
                    dp[j][i] = matrix[j][i];
                } else {
                    dp[j][i] = matrix[j][i] == 0 ? 0 : dp[j - 1][i] + 1;
                }
            }
        }

        int result = 0;
        for (int i = 0; i < rows; i++) {
            Deque<Integer> stack = new LinkedList<>();
            for (int j = 0; j <= cols; j++) {
                int curr = j == cols ? 0 : dp[i][j];
                while (!stack.isEmpty() && dp[i][stack.peekFirst()] >= curr) {
                    int height = dp[i][stack.pollFirst()];
                    int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                    // if left != 0: j - left + 1
                    result = Math.max(result, height * (j - left));
                }
                stack.offerFirst(j);
            }
        }
        return result;
    }
}

发表于 2025-01-08 10:23:02 回复(0)

Java

牛客148901号

import java.util.*;


public class Solution {
    public int getLargestArea(int[] heights) {
        LinkedList<Integer> stack = new LinkedList<>();
        int maxArea = 0;
        int i = 0;
        while (i <= heights.length) {
            int h = (i == heights.length) ? 0 : heights[i];
            if (stack.isEmpty() || h >= heights[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
        }
        return maxArea;
    }

    public int maximalRectangle (int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int maxArea = 0;
        int[] heights = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            maxArea = Math.max(maxArea, getLargestArea(heights));
        }
        return maxArea;
    }
}

发表于 2024-05-12 16:22:58 回复(0)

不早睡觉不改名

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix int整型二维数组
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int maximalRectangle(int** matrix, int matrixRowLen, int* matrixColLen ) {
    // write code here
    int heights[*matrixColLen + 2];
    int stack[*matrixColLen + 2];
    int top = -1;
    int max = 0;
    heights[0] = 0;
    heights[*matrixColLen + 1] = 0;
    for (int j = 0; j < *matrixColLen + 2; j++) {
        heights[j] = 0;
    }
    for (int i = 0; i < matrixRowLen; i++) {
        //制作直方图
        heights[0] = 0;
        heights[*matrixColLen + 1] = 0;
        for (int j = 0; j < *matrixColLen; j++) {
            if (matrix[i][j] > 0)
                heights[j + 1] += matrix[i][j];
            else
                heights[j + 1] = 0;
        }
        //计算最大矩形
        for (int j = 0; j < *matrixColLen + 2; j++) {
            while (top != -1 && heights[j] <= heights[stack[top]]) {
                if (top == 0 && j < *matrixColLen + 1)
                    break;
                // 获取栈顶元素对应的高
                int curHeight = heights[stack[top--]];
                // 栈顶元素弹出后，新的栈顶元素就是其左侧边界
                int leftIndex = stack[top];
                // 右侧边界是当前考察的索引
                int rightIndex = j;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;

                // 计算面积
                max = curWidth * curHeight > max ? curWidth * curHeight : max;
            }
            stack[++top] = j;
        }
    }
    return max;
}

发表于 2022-07-27 12:04:02 回复(0)

布加迪.威龙

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @return int整型
     */
    int maximalRectangle(vector<vector<int> >& matrix) {
        // write code here
        int maxArea = 0;
        
        int m = matrix.size();
        int n = matrix[0].size();
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j]){
                    if(j)
                        matrix[i][j] = matrix[i][j - 1] + 1;
                    int len = matrix[i][j];
                    int height = 1;
                    while(i - height + 1 >= 0 && matrix[i - height + 1][j]){
                        len = min(len, matrix[i - height + 1][j]);
                        maxArea = max(maxArea, len * height);
                        ++height;
                    }
                }
            }
        }
        
        return maxArea;
    }
};

发表于 2022-07-19 09:10:51 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=196&tqId=39479&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 构建动态规划矩阵
            设dp[i][j]表示第i行以元素matrix[i][j]结尾的连续1的个数
            状态转移方程：
                若matrix[i][j] == 0:
                    dp[i][j] = 0
                否则：
                     dp[i][j] = 1 if j == 0 else dp[i][j - 1] + 1
        2. 遍历矩阵dp，对于dp[i][j]，我们从第i行枚举到0行，不断计算以matrix[i][j]为右下角的最大矩形面积，并更新res
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def maximalRectangle(self, matrix):
        # write code here
        m, n = len(matrix), len(matrix[0])

        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if matrix[i][0] == 1:
                dp[i][0] = 1
        for i in range(m):
            for j in range(1, n):
                if matrix[i][j] == 1:
                    dp[i][j] = dp[i][j - 1] + 1
        # print dp

        res = 0
        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    continue
                area, width = dp[i][j], dp[i][j]
                for k in range(i - 1, -1, -1):
                    width = min(width, dp[k][j])
                    area = max(area, width * (i - k + 1))
                res = max(res, area)
        return res


if __name__ == "__main__":
    sol = Solution()

    # matrix = [[1]]

    # matrix = [[1, 1], [0, 1]]

    # matrix = [[0, 0], [0, 0]]

    matrix = [[1, 0, 1, 0, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]

    res = sol.maximalRectangle(matrix)

    print res

发表于 2022-07-03 13:14:58 回复(0)

窓

class Solution:
    def maximalRectangle(self, matrix):
        # 预处理，使每个元素的值表示从当前位置开始向上数，连续的1的个数
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = matrix[i - 1][j] + 1 if matrix[i][j] else matrix[i][j]
        maxRec = 0
        for line in matrix:
            for i in range(len(line)):
                # 对每个>0的元素，向左求他和左边的元素能组成的最大矩形，碰到0停止
                if line[i] > 0:
                    x = 0
                    j = i
                    minH = line[i]
                    while j >= 0 and line[j] > 0:
                        minH = min(minH, line[j])
                        x += 1
                        j -= 1
                        maxRec = max(maxRec, x * minH)
        return maxRec

发表于 2022-03-13 17:47:06 回复(0)

Java

属于你的表演

压缩矩阵

暴力求解的时间复杂度为 O(M^3*N^3)

该解法的时间复杂度为O(N^2*M)

从矩阵第一行开始到matrix[0].length行遍历矩阵

再从矩阵第二行开始到matrix[0].length行遍历矩阵

............一直到最后一行

用arr[]来存储矩阵的类加值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        // write code here
        int maxS=0;
        for(int i=0;i<matrix.length;i++){
            int[] arr=new int[matrix[0].length];
            for(int j=i,row=1;j<matrix.length;j++){
                int sum=0;
                for(int k=0;k<matrix[0].length;k++){
                    arr[k]+=matrix[j][k];
                    if(arr[k]==row){
                        sum+=arr[k];
                        maxS=Math.max(maxS,sum);
                    }else{
                        sum=0;
                    }
                }
                row++;
            }
        }
        return maxS;
    }
}

发表于 2022-03-08 16:16:49 回复(0)

6390455

class Solution:
    def maximalRectangle(self , matrix: List[List[int]]) -> int:
        # write code here

        m = len(matrix)
        if not m:
            return 0
        n = len(matrix[0])
        dp = [0]*n
        ans = 0
        for i in range(m):
            for j in range(n):
                dp[j] = 0 if matrix[i][j] == 0 else dp[j]+1
            ans = max(ans,self.compute_Area(dp))
        return ans

    def compute_Area(self,heights):
        stack = [(-1,-1)]
        H = heights+[0]
        ans = 0
        for i,h in enumerate(H):
            while stack[-1][1]>h:
                _,oh = stack.pop()
                s = (i-stack[-1][0]-1)*oh
                ans = max(ans,s)
            stack.append((i,h))
        return ans

发表于 2022-02-17 16:17:51 回复(0)

最大矩形

输入

输出

输入

输出

说明

输入

输出

输入

输出

单调栈（算法流程）

复杂度分析

问题信息

热门推荐

通过挑战的用户

相关试题