题目：
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
代码：
class Solution {public: int maximalRectangle(vector >& matrix) { if (matrix.empty()) return 0; const int ROW = matrix.size(); const int COL = matrix[0].size(); vector height(COL,0); vector l_most(COL,0); vector r_most(COL,COL-1); int max_area = 0; for ( int i = 0; i < ROW; ++i ) { int l_curr = 0; int r_curr = COL-1; // calculate current row's height for ( int j = 0; j < COL; ++j ) { height[j] = matrix[i][j]=='1' ? height[j]+1 : 0; } // from left to right for ( int j = 0; j < COL; ++j ) { if ( matrix[i][j]=='1' ) { l_most[j] = std::max(l_most[j], l_curr); } else { l_most[j] = 0; l_curr = j+1; } } // from right to left for ( int j = COL-1; j>=0; --j ) { if ( matrix[i][j]=='1' ) { r_most[j] = std::min(r_most[j], r_curr); } else { r_most[j] = COL-1; r_curr = j-1; } } // calculate area of rectangle for ( int j = 0; j tips：
学习了网上的O(m×n)时间复杂度的解法。
这道题的路子类似于
总体的思路如下：
每次遍历一行的元素，以这一行作为X轴；模仿largest rectangle in histogram这道题
大体思路如下，需要对largest rectangle in histogram这道题有比较深刻的理解
a) 计算每个点的当前高度
b) 计算当前高度下每个点能往左推到哪个位置
c) 计算当前高度下每个点能往右推到哪个位置
d) 遍历以当前行作为X轴可能获得的最大面积
a)~d)走完所有行，就可以获得最大的矩形面积
思路实在精妙，详细记录下思考每个环节的过程：
a) 如何计算当前点的高度？
利用滚动数组技巧：height[j]记录的是到i-1行该列对应的高度；如果matrix[i][j]=='1'，则height[j] += 1，即比上一行该列位置+1；如果matrix[i][j]=='0'则对于第i行来说，该列对应的高度就是0。这个道理比较直观，简单说就是滚动数组height[j]的更新原则是看高度能不能在新的一行续上。这种滚动数组技巧的好处在于只需要维护一个一维数组，否则需要维护二维数组，是dp过程的常用技巧。
b) c) 如何找每个点向左（右）能推到的最远的位置？
这个部分更是精妙，不仅利用了滚动数组的技巧，而且还充分利用了上一轮dp的结果。以b)为例分析，c)同理。
在此题的背景下，当前行的某列能向左推到哪要考虑如下几种情况：
1）高度是是0（即matrix[i][j]=='1'不成立）：显然能推到最左侧即0的位置，不受上一行该列能向左推到哪的影响。
2）如果高度不是0（即matrix[i][j]=='1'成立），则这当前行该列能向左推到哪取决于左侧第一个不比它高的列在哪？
考虑一个问题：在matrix[i][j]=='1'的前提下，第i行的l_most[j]可不可能比第i-1行的l_most[j]还小（即还往左）？
显然，这是不可能的。因为第i行的j列已经把高度续上了，当且仅当第i行l_most[j]~j列的位置都满足高度续上的前提下，第i行的l_most[j]才可能等于第i-1行的l_most[j]；一旦第i行l_most[j]~j有一个位置没有续上高度，那么第i行的l_most[j]就要比第i-1行的l_most[j]小了.
通过以上分析，在第i行j列已经把高度续上的前提下，能向左推到哪，关键取决于在j左边且最靠近j列没续上高度的列，是否影响到了l_most[j]~j。因此，维护一个l_curr，标记到当前列为止，续上高度的列最多可能向左推到哪。
所以，需要比较l_most[j]与l_curr的位置。如果遇上了高度为0的，则自动把l_curr+1；如果高度不为0的，判断l_curr是否影响到了l_most[j]
描述的比较绕口，但是客观上也就是这样了。
d) 计算可能的最大高度
这个就是个常规的dp，不再赘述了。注意一点就是（right-left+1）*height，这里是否“+1”取决于l_most和r_most的取值方式。
==============================================
第二次过这道题，思路记得比较清晰；具体操作上一些细节再熟练一下。
class Solution {public: int maximalRectangle(vector >& matrix) { int ret = 0; if ( matrix.empty() ) return ret; vector height(matrix[0].size(), 0); for ( int i=0; i