Leetcode209: Maximal Rectangle

本文主要是介绍Leetcode209: Maximal Rectangle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

给定一个矩阵中，只有0和1，求出这个矩阵的一个最大的子矩阵，其中只包含1.

例如

01101

11010

01110

11110

11111

00000

其实这个问题可以转化为Largest Rectangle in Histogram，先将上面的矩阵转化为：

01101

12010

03110

14210

25321

00000

然后对每一行求直方图的最大面积。

class Solution {
public:int maxArea(vector<int> &line) {if (line.size() < 1) return 0;stack<int> S;line.push_back(0);int sum = 0;for (int i = 0; i < line.size(); i++) {if (S.empty() || line[i] > line[S.top()]) S.push(i);else {int tmp = S.top();S.pop();sum = max(sum, line[tmp]*(S.empty()? i : i-S.top()-1));i--;}}return sum;}int maximalRectangle(vector<vector<char> > &matrix) {if (matrix.size() < 1) return 0;int n = matrix.size();if (n == 0) return 0;int m = matrix[0].size();if (m == 0) return 0;vector<vector<int> > lines(n, vector<int>(m, 0));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (i == 0) {lines[i][j] = ((matrix[i][j] == '1') ? 1 : 0);} else {lines[i][j] += ((matrix[i][j] == '1') ? lines[i-1][j] + 1 : 0);}}}int maxRec = 0, tmpRec;for (int i = 0; i < n; ++i) {tmpRec = maxArea(lines[i]);maxRec = (maxRec > tmpRec) ? maxRec : tmpRec;}return maxRec;}
};

这篇关于Leetcode209: Maximal Rectangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---