Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
思路：
例如
01101
11010
01110
11110
11111
00000
按列从上到下计算maximal rectangle：
01101
12010
03110
14210
25321
00000
然后对每一行求直方图的最大面积，于是这个问题可以转化为Largest Rectangle in Histogram。
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
if(height.size() == ) return ;
int res = ;
stack<int> idxStack;
height.push_back(); //为了如果在最后height为最高的情况，能够再进一次else，把stack中的元素pop出来计算
for(int i = ; i < height.size(); i++)
{
if(idxStack.empty() || (!idxStack.empty() && height[i] >= height[idxStack.top()])) //当前高度>=栈顶高度
idxStack.push(i); //入栈
else{ //高度降低了,那么再之后也就不可能超过height[idx],所以看之前的高度*宽度能够达到怎样的值
while(!idxStack.empty() && height[idxStack.top()] > height[i]) //只要当前高度<栈顶高度
{
int idx = idxStack.top();
idxStack.pop();
int width = idxStack.empty() ? i : (i-idxStack.top()-); //当前index-1的位置（目前为止最高高度的位置）到当前栈顶元素的位置的宽度
res = max(res, height[idx] * width);
}
idxStack.push(i);
}
}
height.pop_back();
return res;
}
int maximalRectangle(vector<vector<char> > &matrix) {
if (matrix.size() < ) return ;
int n = matrix.size();
if (n == ) return ;
int m = matrix[].size();
if (m == ) return ;
vector<vector<int> > lines(n, vector<int>(m, ));
for (int i = ; i < n; ++i) {
for (int j = ; j < m; ++j) {
if (i == ) {
lines[i][j] = ((matrix[i][j] == '') ? : );
} else {
lines[i][j] += ((matrix[i][j] == '') ? lines[i-][j] + : );
}
}
}
int maxRec = , tmpRec;
for (int i = ; i < n; ++i) {
tmpRec = largestRectangleArea(lines[i]);
maxRec = (maxRec > tmpRec) ? maxRec : tmpRec;
}
return maxRec;
}
};