给定一个仅包含 0 和 1 ，大小为 n*m 的二维二进制矩阵，找出仅包含 1 的最大矩形并返回面积。
数据范围：
保证输入的矩形中仅含有 0 和 1
例如输入[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]时，对应的输出为8，所形成的最大矩形如下图所示：
[编程题]最大矩形
/**
* 最大矩形面积 | 最大全一矩形面积
*
* 算法二：动态规划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)
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)
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)
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)
压缩矩阵
暴力求解的时间复杂度为 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)
单调栈（算法流程）
先做一个预处理，计算每个位置包括自己在内，往右有多少个连续的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)
问题信息
难度：
6条回答
57收藏
4620浏览
通过挑战的用户
查看代码-
2022-09-14 10:11:49
-
2022-09-14 01:35:03 -
2022-09-13 16:29:07 -
2022-09-07 15:19:18
-
2022-09-06 19:45:46
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
