雨打梨花深闭门
忘了青春
误了青春
套84的解法，以每一行往上作为柱状图，每列网上连续的‘1’为柱。
需要注意的是，heights的更新使用dp，不然还是超时。。。
class Solution {
private:
vector<int> getEdge(vector<int> &heights, int step) {
vector<int> hash(heights.size(), -1);
stack<int> s;
int start = step > 0 ? 0 : heights.size() - 1;
int end = step > 0 ? heights.size() - 1 : 0;
for (int i = start; i != end + step; i += step) {
while (!s.empty() && heights[s.top()] >= heights[i])
s.pop();
if (s.empty()) hash[i] = start;
else hash[i] = s.top() + step;
s.push(i);
}
return hash;
}
int leetcode84(vector<int>& heights) {
int ans = 0;
vector<int> hash1 = getEdge(heights, 1);
vector<int> hash2 = getEdge(heights, -1);
for (int i = 0; i < heights.size(); i++)
ans = max(ans, heights[i] * (hash2[i] - hash1[i] + 1));
return ans;
}
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = 0, ans = 0;
if (m) n = matrix[0].size();
else return 0;
vector<int> heights(n, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
}
ans = max(ans, leetcode84(heights));
}
return ans;
}
};
