LeetCode 85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:

Input:
[
[“1″,”0″,”1″,”0″,”0”],
[“1″,”0″,”1″,”1″,”1”],
[“1″,”1″,”1″,”1″,”1”],
[“1″,”0″,”0″,”1″,”0”]
]
Output: 6

解析：
此题目是LeetCode 84的升级版本，这道题的二维矩阵每一层向上都可以看做一个直方图，输入矩阵有多少行，就可以形成多少个直方图，对每个直方图都调用 Largest Rectangle in Histogram 中的方法，就可以得到最大的矩形面积。那么这道题唯一要做的就是将每一层都当作直方图的底层，并向上构造整个直方图，由于题目限定了输入矩阵的字符只有 ‘0’ 和 ‘1’ 两种，所以处理起来也相对简单。方法是：对于每一个点，如果是 ‘0’，则赋0，将之前height中值清零；如果是 ‘1’，就赋之前的 height 值加上1。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
int maximalRectangle(vector>& matrix) {
int len = matrix.size();
vector heights;
int ans = 0;
for(int i=0; i < len; i++) { heights.resize(matrix[i].size()); for(int j=0; j < matrix[i].size(); j++) { heights[j] = matrix[i][j] == '0'?0:(1+heights[j]); } ans = max(ans, largestRectangleArea(heights)); } return ans; } int largestRectangleArea(vector& heights) {
if(heights.size() == 0)
return 0;
heights.push_back(0);
int len = heights.size();
int ans = 0;
stack st;
for(int i=0; i < len; i++) { while(!st.empty() && heights[i] < heights[st.top()]) { int val = st.top(); st.pop(); ans = max(ans, heights[val]*(i-1-(st.empty()?-1:st.top()))); } st.push(i); } return ans; } }; [/cc] 运行结果：
参考：
https://www.cnblogs.com/grandyang/p/4322667.html