求二维数组中最大的矩形
对每列的连续1进行累加，问题转化为直方图中求最大矩形，faster than 90%
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
if(matrix.length === 0) return 0
var h = matrix[0].map(item => item - '0')
var max = subMax(h)
for(var i = 1; i < matrix.length; i++){
for(var j = 0; j < matrix[0].length; j++){
if(matrix[i][j] === '1') h[j]++
else h[j] = 0
}
max = Math.max(max, subMax(h))
}
return max
};
var subMax = function(h){
var arr = h.concat([0])
var stack = []
var res = 0
for(var i = 0; i < arr.length; i++){
if(stack.length === 0 || arr[i] >= arr[stack[stack.length - 1]]){
stack.push(i)
}else{
var index = stack[stack.length - 1]
stack.pop()
res = Math.max(res, arr[index] * (stack.length === 0 ? i : (i - stack[stack.length - 1] - 1)))
i--
}
}
return res
}
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
if(matrix.length === 0) return 0
var h = Array(matrix[0].length).fill(0)
var max =0
for(var i = 0; i < matrix.length; i++){
for(var j = 0; j < matrix[0].length; j++){
if(matrix[i][j] === '1') h[j]++
else h[j] = 0
var height = h[j]
for(var k = j; k >= 0; k--){
height = Math.min(height, h[k])
var width = j - k + 1
max = Math.max(max, height * width)
}
}
}
return max
};
