0085. 最大矩形 [Hard] [Maximal Rectangle].md

85. 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.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

---

题目：最大矩形面积。

思路：同84. Largest Rectangle in Histogram。分别以第一行，第一行至第二行，第一行至第三行...构建直方图，计算其最大的矩形区域。

工程代码下载

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        const int m = matrix.size();
        if(m == 0) return 0;
        const int n = matrix[0].size();

        vector<int> heights(n, 0);
        int res = 0;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == '0')
                    heights[j] = 0;
                else
                    heights[j] += 1;
            }
            res = max(res, helper(heights));
        }

        return res;
    }
private:
    int helper(vector<int>& nums){
        const int n = nums.size();
        vector<int> left(n, -1);
        stack<int> sk;

        // 注意循环是倒序的
        for(int i = n-1; i >=0; --i){
            while(!sk.empty() && nums[i] < nums[sk.top()]){
                left[sk.top()] = i;
                sk.pop();
            }
            sk.push(i);
        }

        vector<int> right(n, n);
        stack<int> sk1;
        for(int i = 0; i < n; ++i){
            while(sk1.empty() && nums[i] < nums[sk.top()]){
                right[sk.top()] = i;
                sk.pop();
            }
            sk.push(i);
        }

        int res = 0;
        for(int i = 0; i < n; ++i){
            res = max(res, nums[i]*(right[i] - left[i] - 1));
        }

        return res;
    }
};