Problem
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
return 6
Think
这个问题对我而言还是有一点难度的，主要参考了youtube上的一个视频：https://www.youtube.com/watch?v=g8bSdXCG-lA&t=71s
这个问题解答可以分解为两个步骤，在这之前需要考虑一个叫做
max Area Rectangle in histogram的问题（直方图中最大的矩形面积）
这个问题的描述用一个图还是一目了然的，不需要太多解释．
image.png
现在我们假设解决了max Area Rectangle in histogram，现在考虑怎么解决本来需要解决的问题．
现在有输入数据：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
- 用一个dp数组保存＂直方图＂数据,数组的大小与行同长(len(dp) == 5) dp[i]可以理解为以第i 行为x轴绘制的直方图纵轴高度数据．
- 依照行循环
第1次循环 dp[0] = [1,0 ,1, 0, 0 ]
第２次： dp[1] = [2, 0, 2, 1, 1]
第３次： dp[2] = [3, 1, 2, 2, 2]
第４次： dp[3] = [4, 0, 0, 3, 0] - 依次计算上述四次循环中dp数据的max Area Rectangle in histogram值，四次循环中的最大值就是最终答案
max Area Rectangle in histogram 问题
这个问题其实也并不简单，特别是如果要用O(N)复杂度解决问题的话，还是比较考验智商的．
关于这个问题的解决方案可以参考：
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
这个是一个非常巧妙的解决方案，基本思想是使用stack
// The main function to find the maximum rectangular area under given
// histogram with n bars
int getMaxArea(int hist[], int n)
{
// Create an empty stack. The stack holds indexes of hist[] array
// The bars stored in stack are always in increasing order of their
// heights.
stack<int> s;
int max_area = 0; // Initalize max area
int tp; // To store top of stack
int area_with_top; // To store area with top bar as the smallest bar
// Run through all bars of given histogram
int i = 0;
while (i < n)
{
// If this bar is higher than the bar on top stack, push it to stack
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
// If this bar is lower than top of stack, then calculate area of rectangle
// with stack top as the smallest (or minimum height) bar. 'i' is
// 'right index' for the top and element before top in stack is 'left index'
else
{
tp = s.top(); // store the top index
s.pop(); // pop the top
cout<<"the top is:"<<hist[tp]<<endl;
// Calculate the area with hist[tp] stack as smallest bar
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
cout<<"max area:"<<area_with_top<<endl;
// update max area, if needed
if (max_area < area_with_top)
max_area = area_with_top;
}
}
// Now pop the remaining bars from stack and calculate area with every
// popped bar as the smallest bar
while (s.empty() == false)
{
tp = s.top();
s.pop();
cout<<"top is:"<<hist[tp]<<endl;
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
cout<<"area:"<<area_with_top<<endl;
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
int main(){
int hist[] = {4,2,5,3,1,6};
int n = sizeof(hist)/sizeof(hist[0]);
cout << "Maximum area is " << getMaxArea(hist, n)<<endl;
return 0;
}
参考资源：https://www.youtube.com/watch?v=KkJrGxuQtYo
这里所使用的原理是： 对于每一个高度，计算在这个高度上能够达到的最大面积值，然后在这些最大面积值中进行比较，得出最终结果．在某一个高度上能够带到的最大面积由＂边界＂决定，所谓边界指的是两边的高度都比指定高度要低．
Code
class Solution(object):
def maxAreaRectangle(self, seq):
# type(seq): list(int)
# list[i] represent height at i
max_area = -1
i = 0
stack = []
while i < len(seq):
if len(stack) == 0 or seq[stack[-1]] <= seq[i]:
stack.append(i)
i += 1
else:
tp = stack.pop()
area_with_top = seq[tp] * (i if len(stack) == 0 else (i - stack[-1] - 1))
if area_with_top > max_area:
max_area = area_with_top
while len(stack) > 0:
tp = stack.pop()
area_with_top = seq[tp] * (i if len(stack) == 0 else (i - stack[-1] - 1))
if area_with_top > max_area:
max_area = area_with_top
return max_area
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
ans = -1
dp = []
for i in range(m):
if i == 0:
for j in range(n):
dp.append(int(matrix[i][j]))
else:
new_dp = []
for j in range(n):
if dp[j] != 0 and matrix[i][j] == '1':
new_dp.append(dp[j] + 1)
else:
new_dp.append(int(matrix[i][j]))
dp = new_dp
level_max = self.maxAreaRectangle(dp)
if level_max > ans:
ans = level_max
return ans
``` 
网友评论