给定一个仅包含 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,所形成 的最大矩形如下图所示:-笔试面试资料

这是qklbishe.com第19427 篇笔试面试资料
提供答案分析,通过本文《给定一个仅包含 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,所形成 的最大矩形如下图所示:-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个仅包含 0 和 1 ,大小为 n*m 的二维二进制矩阵,找出仅包含 1 的最大矩形并返回面积。
数据范围:给定一个仅包含 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,所形成 的最大矩形如下图所示: 保证输入的矩形中仅含有 0 和 1
例如输入[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]时,对应的输出为8,所形成的最大矩形如下图所示:
给定一个仅包含 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,所形成 的最大矩形如下图所示:
Java

给定一个仅包含 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,所形成 的最大矩形如下图所示: 零葬

单调栈(算法流程)

先做一个预处理,计算每个位置包括自己在内,往右有多少个连续的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)。

今天 13:10:22 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个仅包含 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,所形成 的最大矩形如下图所示:-笔试面试资料

提供最优质的资源集合

立即查看 了解详情