0 1 0 0
1 1 1 0
0 1 1 0
0 0 1 0
0 1 0 0
对于上述这个矩阵，我们人脑是如何第一时间发现中间那坨 1 的呢？我觉得应该有下面这个过程:
_
0 1 0 0 | |_
1 1 1 0 |*|*|
0 1 1 0 |*|*|
---------------
0 0 1 0
0 1 0 0
首先一眼排除掉虚线下面的可能性，而上面的部分，怎么看怎么像是 [114. Largest Rectangle in Histogram](../114. Largest Rectangle in Histogram) 的图。显然如果将层数累加，则成了 height 这个 vector 了。
0 3 2 0
这就完全成了 114 题的解答了。
所以这道题比较偷懒的方法，是直接使用 114 题里的 largestRectangleArea 方法。并构建出 height 这个 vector 即可。
大部分童鞋和我一样，遇到这道题的时候，还没遇到 114, 那么灵感应该不会那么突然，常规的思路应该还是 DP。
但对于 DP, 我一直都未找到很好的解决方案。留作日后补充。
#include <vector>
using std::vector;
#include <stack>
using std::stack;
#include <algorithm>
using std::max; using std::min;
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int max_area = 0, i = 0, size = height.size();
for (stack<int> stk; i<size || !stk.empty(); )
if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++);
else {
int tp = stk.top(); stk.pop();
max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
}
return max_area;
}
int maximalRectangle(vector<vector<char> > &matrix) {
if (matrix.empty()) return 0;
int max_area = 0;
vector<int> height(matrix[0].size(), 0);
for (size_t i=0; i<matrix.size(); ++i) {
for (size_t j=0; j<matrix[0].size(); ++j)
if (matrix[i][j] == '0') height[j] = 0;
else ++height[j];
max_area = max(max_area, largestRectangleArea(height));
}
return max_area;
}
};