85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 C++代码如下：

class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { if(!matrix.size()||!matrix[0].size()) return 0; int matrix_H=matrix.size(); int matrix_W=matrix[0].size(); int maxNum=0; vector<int> DP_heights(matrix_W,0); for(int i=0;i<matrix_H;i++) { for(int j=0;j<matrix_W;j++) { DP_heights[j]=(matrix[i][j]=='1' ? DP_heights[j]+1:0); } maxNum=max(maxNum,maxNumForRow(DP_heights)); } return maxNum; } int maxNumForRow(vector<int>& DP_heights) { int maxNum=0; stack<int> my_stack; my_stack.push(-1); for (int i=0;i<DP_heights.size();i++) { while(my_stack.top()!=-1 && DP_heights[my_stack.top()]>=DP_heights[i]) { int height=DP_heights[my_stack.top()]; my_stack.pop(); int topIndex=my_stack.top(); maxNum=max(maxNum,height*(i-topIndex-1)); } my_stack.push(i); } while(my_stack.top()!=-1) { int height=DP_heights[my_stack.top()]; my_stack.pop(); int topIndex=my_stack.top(); int right=DP_heights.size(); maxNum=max(maxNum , height*(right-topIndex-1)); } return maxNum; } };

运行效果（渣渣）：

搞了我一上午（阅读理解），还要多加练习啊。