Given a 2Dbooleanmatrix filled withFalseandTrue, find the largest rectangle containing allTrueand return its area.

Have you met this question in a real interview?

Yes

Example

Given a matrix:

[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]

return6.

class Solution {

public:

/\*\*

 \* @param matrix a boolean 2D matrix

 \* @return an integer

 \*/

int maximalRectangle\(vector<vector<bool> > &matrix\) {

    // Write your code here

    if \(matrix.empty\(\) \|\| matrix\[0\].empty\(\)\) {

        return 0;

    }

    int n = matrix.size\(\), m = matrix\[0\].size\(\);

    vector<vector<int>> heights\(n, vector<int>\(m , 0\)\);

    for \(int i = 0; i < n; ++i\) {

        for \(int j = 0; j < m; ++j\) {

            if \(i == 0\) {

                heights\[i\]\[j\] = matrix\[i\]\[j\] ? 1 : 0;

                continue;

            }

            heights\[i\]\[j\] = matrix\[i\]\[j\] ? heights\[i-1\]\[j\] + 1 : 0;

        }

    }



    int maxArea = 0;

    for \(int i = 0; i < n; ++i\) {

        int area = getMaxAreaInHist\(heights\[i\]\);

        if \(area > maxArea\) {

            maxArea = area;

        }

    }

    return maxArea;

}



int getMaxAreaInHist\(vector<int>& height\) {

    int res = 0;

    stack<int> s;

    height.push\_back\(0\);

    int i = 0;

    while \(i < height.size\(\)\) {

        if \(s.empty\(\) \|\| height\[i\] > height\[s.top\(\)\]\) {

            s.push\(i\);

            ++i;

        } else {

            int h = height\[s.top\(\)\]; s.pop\(\);

            int w = s.empty\(\) ? i : i - s.top\(\) - 1;

            res = max\(res, h \* w\);

        }

    }

    return res;

}

};