LeetCode85 Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. （Hard）

For example, given the following matrix:

Return 6.

分析：

这个题挺不好想的，可以先考虑暴力的做法，遍历所有节点作为可能有的长方形的左上角。

然后对于每个左上角，向下遍历每一行，维护更新一个各个行中向右最少的1的个数，直到不是1的行为止，这样可以计算一个长方形面积。

对于每个左上角计算一下，则可以得到最大长方形面积。

考虑这个做法的时间复杂度，应该是O(n^4)。

进一步优化，发现数组中向右或向下连续1的个数是一个计算问题的关键，考虑能不能实现用数组存好这一数据，再进行计算。

于是发现此题与前一题Largest Rectangle in Histogram有共通之处。

将dp数组存放以此节点开始向下的最长1的个数，则对于每一行，实际就是一个Largest Rectangle in Histogram问题。对于每一行调用上一问题即可。

代码：

 1 class Solution {
 2 private:
 3     int largestRectangleArea(vector<int>& heights) {
 4         int result = 0;
 5         int sz = heights.size(); 
 6         stack<int> s;
 7         for (int i = 0; i < sz; ++i) {
 8             if (s.empty() || heights[i] >= heights[s.top()]) {
 9                 s.push(i);
10             }
11             else {
12                 while (!s.empty() && heights[s.top()] > heights[i]) {
13                     int cur = s.top();
14                     s.pop();
15                     int prev = (s.empty()) ? -1 : s.top();
16                     result = max(result, (i - prev - 1) * heights[cur] );
17                 }
18                 s.push(i);
19             }
20         }
21         while (!s.empty()) {
22             int cur = s.top();
23             s.pop();
24             int prev = (s.empty()) ? -1 : s.top();
25             result = max(result, (sz - prev - 1) * heights[cur] );
26         }
27         return result;
28     }
29 public:
30     int maximalRectangle(vector<vector<char>>& matrix) {
31         if (matrix.size() == 0) {
32             return 0;
33         }
34         int rowSize = matrix.size(), colomnSize = matrix[0].size();
35         vector<vector<int>> dp(rowSize, vector<int>(colomnSize));
36         for (int i = 0; i < rowSize; ++i) {
37             for (int j = 0; j < colomnSize; ++j) {
38                 dp[i][j] = 0;
39                 for (int k = 0; i + k < rowSize && matrix[i + k][j] == '1'; ++k) {
40                     dp[i][j]++;
41                 }
42             }
43         }
44         int result = 0;
45         for (int i = 0; i < rowSize; ++i) {
46             result = max(result, largestRectangleArea(dp[i]));
47         }
48         return result;
49     }
50 };