求最大子矩阵的大小 (maximal-rectangle)

题目:

给定一个整形矩阵map,其中的值只有0和1两种,求其中全是1的所有矩阵区域中,最大的矩形的面积。


例如:图中是一个4 × 6的矩形,画出红色的是我们要找到的区域,结果返回为 4.

      仔细观察发现:因为我们要找的是矩形,所以它一定是以某个行元素开始的,这样的话,其实我们要找到的某个矩形就转换成以某一个行开始的 histogram的最大矩形问题了。

       该问题与histogram的关系与( 连续子序列最大和  和  最大子矩阵和  )情况类似。

                                                                                                                      

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null||matrix.length == 0||matrix[0].length == 0)
            return 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++)
                {
                int height=heightFunc(matrix,i,j);
                dp[i][j]+=height;
                for(int k=j-1;k>=0;k--)
                    {
                    if(heightFunc(matrix,i,k) >= height)
                        {
                        dp[i][j]+=height;
                    }else
                        break;
                }
                for(int k=j+1;k<matrix[0].length;k++)
                    {
                    if(heightFunc(matrix,i,k) >= height)
                        {
                        dp[i][j]+=height;
                    }else
                        break;
                }
            }
        }
        int max=dp[0][0];
            for(int i=0;i<dp.length;i++)
                {
                for(int j=0;j<dp[0].length;j++)
                    {
                    if(dp[i][j] > max)
                        max=dp[i][j];
                }
            }
            return max;
    }
    public int heightFunc(char[][] matrix,int i,int j)
        {
        if(matrix[i][j] == '0')
            return 0;
        int height=0;
        while(i>=0&&matrix[i][j] == '1')
            {
                height++;
                i--;          
        }
        return height;
    }
}


由于所求的值只与作为子矩形的底边的行有关,可以将dp数组压缩成一维。

import java.util.*;
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null||matrix.length == 0||matrix[0].length == 0)
            return 0;
        int[] dp=new int[matrix[0].length];//压缩为一维数组
        int max=0;
        for(int i=0;i<matrix.length;i++)
            {
            Arrays.fill(dp,0);//每次更新底边i时,将dp清空。
            for(int j=0;j<matrix[0].length;j++)//简单的一维histogram求法
                {
                int height=heightFunc(matrix,i,j);
                dp[j]+=height;
                for(int k=j-1;k>=0;k--)
                    {
                    if(heightFunc(matrix,i,k) >= height)
                        {
                        dp[j]+=height;
                    }else
                        break;
                }
                for(int k=j+1;k<matrix[0].length;k++)
                    {
                    if(heightFunc(matrix,i,k) >= height)
                        {
                        dp[j]+=height;
                    }else
                        break;
                }
                if(dp[j] > max)
                    max=dp[j];
            }
        }
            return max;
    }
    public int heightFunc(char[][] matrix,int i,int j)//求高度例程
        {
        if(matrix[i][j] == '0')
            return 0;
        int height=0;
        while(i>=0&&matrix[i][j] == '1')
            {
                height++;
                i--;          
        }
        return height;
    }
}


### 使用单调栈最大子矩阵问题 #### 算法概述 对于给定的一个由 `0` `1` 组成的二维矩阵,目标是找到其中仅包含 `1` 的最大矩形区域并返回其面积。此问题可以通过将二维问题转化为多个一维问题来解决,具体方法如下: 通过逐行遍历矩阵,并利用前缀的思想计算每列的高度(即连续 `1` 的数量),从而构建一个高度数组 `heights[]`。随后,针对每一行的高度数组应用 **单调栈** 来找出当前行所能形成的最大矩形面积。 终的结果是从所有行中得到的最大矩形面积中的最大[^3]。 --- #### 关键步骤解析 ##### 1. 高度数组的构建 定义一个长度等于矩阵宽度的数组 `heights[]`,初始化为零。每次迭代一行时更新该数组,使得 `heights[j]` 表示第 `j` 列从当前位置向上数连续 `1` 的个数。如果遇到 `0`,则重置对应列的高度为零。 ```python def build_heights(matrix, heights): rows, cols = len(matrix), len(matrix[0]) for j in range(cols): # 初始化第一行的高度 heights[j] = int(matrix[0][j]) for i in range(1, rows): # 更新后续行的高度 for j in range(cols): if matrix[i][j] == '1': heights[j] += 1 else: heights[j] = 0 ``` 此处的时间复杂度为 O(m * n),其中 m 是矩阵的行数,n 是列数[^4]。 --- ##### 2. 单调栈的应用 为了高效地解单行内的最大矩形面积,采用单调栈的方法。核心思路是对每个柱状体(代表某一列的高度)寻找左侧第一个小于它的索引 `left_idx` 右侧第一个小于它的索引 `right_idx`,进而计算以其为高的矩形面积 `(right_idx - left_idx - 1) * height[idx]`。 以下是基于单调栈的具体实现逻辑: - 构建一个严格递增的栈; - 当发现新的高度低于栈顶对应的柱高时,弹出栈顶元素并计算以该柱高为基础的矩形面积; - 将新高度压入栈中继续处理。 ```python def max_rectangle_in_histogram(heights): stack = [] max_area = 0 heights.append(0) # 添加哨兵简化边界条件 for idx, h in enumerate(heights): while stack and heights[stack[-1]] >= h: current_height = heights[stack.pop()] width = idx if not stack else (idx - stack[-1] - 1) max_area = max(max_area, current_height * width) stack.append(idx) heights.pop() # 移除哨兵恢复原数组状态 return max_area ``` 上述函数实现了对任意输入的一维直方图最大矩形面积的功能,时间复杂度为 O(n)[^5]。 --- ##### 3. 整合过程 后一步是将以上两部分结合起来完成整个算法流程。依次遍历矩阵的每一行,动态维护高度数组并通过单调栈获取局部优解;全局优解则是这些局部结果中的最大者。 完整代码展示如下: ```python def maximalRectangle(matrix): if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) heights = [0] * cols max_area = 0 def calculate_max_area_with_stack(): nonlocal heights, max_area stack = [] heights.append(0) # 哨兵 for idx, h in enumerate(heights): while stack and heights[stack[-1]] >= h: current_height = heights[stack.pop()] width = idx if not stack else (idx - stack[-1] - 1) max_area = max(max_area, current_height * width) stack.append(idx) heights.pop() # 清理哨兵 for row in matrix: for j in range(cols): heights[j] = heights[j] + 1 if row[j] == '1' else 0 calculate_max_area_with_stack() return max_area ``` 整体时间复杂度为 O(m * n),空间复杂度主要取决于辅助使用的栈结构以及存储高度信息的数据结构,均为线性级别。 --- ### 结果验证 考虑样例输入: ``` [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] ``` 执行上述程序可得出正确答案 `6`,与预期一致[^2]。 ---
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值