给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例:
输入:[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]输出: 6 解答:对于此类问题,可以用递归来处理。这个问题可以转化成求柱状图的最大面积,具体转化方式如下: 以列为单位构建柱状图高度,若 v[m][n] 对应点的值为0,那么 v[m+1][n]的高度值需要重新统计;否则高度值进行累加。 然后通过对构建的每一行柱状图采用求最大面积的求法得出结果。
int maximalRectangleHelper(vector height){ int res = 0; height.push_back(0); stack s; for(int i=0;i<(signed)height.size();i++) { if(s.empty() || height[s.top()] < height[i] ) s.push(i); else { int curr = s.top(); s.pop(); res = max(res, height[curr] * (s.empty()?i: i-s.top()-1)); i--; } } return res;}//85int maximalRectangle(vector>& matrix){ if(matrix.empty() || matrix[0].empty()) return 0; int m = matrix.size(), n = matrix[0].size(); vector height(n,0); int res=0; for(int i=0;i