javascript - 求最大全1子矩阵中1的个数
本文介绍了javascript - 求最大全1子矩阵中1的个数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
给定一个01矩阵map,求其中全是1的子矩阵里1的最大个数。
例如:
1 1 1 0
其中最大的全1子矩阵有3个1,返回3.
1 0 1 1
1 1 1 1
1 1 1 0
其中最大的全1子矩阵有6个1,返回6.
对于N*M的01矩阵,求时间复杂度为O(N*M)的Javascript实现方案
解决方案
function getMaxMatrix(map){
if(map == null || map.length == 0 || map[0].length == 0) return 0;
var maxArea = 0;
var height = [];
for(var k = 0; k < map[0].length; k++){
height[k] = 0;
}
for(var i = 0; i < map.length; i++){
for(var j = 0; j < map[0].length; j++){
height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
}
maxArea = Math.max(maxMatrixFromBottom(height), maxArea);
}
return maxArea;
}
function maxMatrixFromBottom(height){
if(height == null || height.length == 0) return 0;
var maxArea = 0;
var stack = [];
for(var i = 0; i < height.length; i++){
while(stack.length != 0 && height[i] <= height[stack[stack.length - 1]]){
var j = stack.pop();
var k = stack.length == 0 ? -1 : stack[stack.length - 1];
var curArea = (i - k -1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack.push(i);
}
while(stack.length != 0){
var j = stack.pop();
var k = stack.length == 0 ? -1 : stack[stack.length - 1];
var curArea = (i - k -1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
var map =[
[1,1,1,1],
[1,1,1,1],
[1,0,0,0]
];
console.log(getMaxMatrix(map))
这篇关于javascript - 求最大全1子矩阵中1的个数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文