# algorithm - 找到N×N二进制矩阵中仅包含零的最大矩形

## arrays (4)

``````      I
0 0 0 0 1 0
0 0 1 0 0 1
II->0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 1 <--IV
0 0 1 0 0 0
IV
``````

``````public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if (m == 0)
return 0;
int n = matrix[0].length;
int maxArea = 0;
int[] aux = new int[n];
for (int i = 0; i < n; i++) {
aux[i] = 0;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
aux[j] = matrix[i][j] - '0' + aux[j];
maxArea = Math.max(maxArea, maxAreaHist(aux));
}
}
return maxArea;
}

public int maxAreaHist(int[] heights) {
int n = heights.length;
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
int maxRect = heights[0];
int top = 0;
int leftSideArea = 0;
int rightSideArea = heights[0];
for (int i = 1; i < n; i++) {
if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
stack.push(i);
} else {
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
top = stack.pop();
rightSideArea = heights[top] * (i - top);
leftSideArea = 0;
if (!stack.isEmpty()) {
leftSideArea = heights[top] * (top - stack.peek() - 1);
} else {
leftSideArea = heights[top] * top;
}
maxRect = Math.max(maxRect, leftSideArea + rightSideArea);
}
stack.push(i);
}
}
while (!stack.isEmpty()) {
top = stack.pop();
rightSideArea = heights[top] * (n - top);
leftSideArea = 0;
if (!stack.isEmpty()) {
leftSideArea = heights[top] * (top - stack.peek() - 1);
} else {
leftSideArea = heights[top] * top;
}
maxRect = Math.max(maxRect, leftSideArea + rightSideArea);
}
return maxRect;
}
``````

``````#!/usr/bin/env python3

import numpy

s = '''0 0 0 0 1 0
0 0 1 0 0 1
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 1
0 0 1 0 0 0'''

nrows = 6
ncols = 6
skip = 1
area_max = (0, [])

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
for c in range(ncols):
if a[r][c] == skip:
continue
if r == 0:
h[r][c] = 1
else:
h[r][c] = h[r-1][c]+1
if c == 0:
w[r][c] = 1
else:
w[r][c] = w[r][c-1]+1
minw = w[r][c]
for dh in range(h[r][c]):
minw = min(minw, w[r-dh][c])
area = (dh+1)*minw
if area > area_max[0]:
area_max = (area, [(r-dh, c-minw+1, r, c)])

print('area', area_max[0])
for t in area_max[1]:
print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))
``````

``````area 12
Cell 1:(2, 1) and Cell 2:(4, 4)
``````

[算法]通过从上到下迭代行来工作，每行解决这个问题 ，其中“直方图”中的“条形”由从当前行开始的所有零的不间断向上轨迹组成（列具有高度0如果它在当前行中有1）。

``````#!/usr/bin/env python
from collections import namedtuple
from operator import mul

Info = namedtuple('Info', 'start height')

def max_size(mat, value=0):
"""Find height, width of the largest rectangle containing all `value`'s."""
it = iter(mat)
hist = [(el==value) for el in next(it, [])]
max_size = max_rectangle_size(hist)
for row in it:
hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
max_size = max(max_size, max_rectangle_size(hist), key=area)
return max_size

def max_rectangle_size(histogram):
"""Find height, width of the largest rectangle that fits entirely under
the histogram.
"""
stack = []
top = lambda: stack[-1]
max_size = (0, 0) # height, width of the largest rectangle
pos = 0 # current position in the histogram
for pos, height in enumerate(histogram):
start = pos # position where rectangle starts
while True:
if not stack or height > top().height:
stack.append(Info(start, height)) # push
elif stack and height < top().height:
max_size = max(max_size, (top().height, (pos - top().start)),
key=area)
start, _ = stack.pop()
continue
break # height == top().height goes here

pos += 1
for start, height in stack:
max_size = max(max_size, (height, (pos - start)), key=area)
return max_size

def area(size):
return reduce(mul, size)
``````