Explanation with diagram
\n\n\n1. Every row can be converted into a histogram very easily. Total time taken for this operation will be O(rows * cols).\n2. Then for every histogram we ca
![image](https://assets.leetcode.com/users/images/468d99fd-4348-4866-8b8c-9609d3293cfd_1648020077.274421.png)\n\n\n1. Every row can be converted into a histogram very easily. Total time taken for this operation will be **O(rows * cols)**.\n2. Then for every histogram we can find the largest area of rectangle in it. We can find the largest area of rectangle in histogram in **O(cols)** time using monotonous stack. So the total time complexity for finding largest area of reactangle in every histogram will be **O(rows * cols)**.\n3. Max rectangle will be the largest area of histogram among all histograms.\n\nTime Complexity: O(rows * cols)\nSpace Complexity: O(rows * cols)\n\n```\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int rows = matrix.size(), cols = matrix[0].size();\n\n        vector<vector<int>> rowHeights(rows, vector(cols, 0));\n        \n\t\t// convert every row into a histogram\n        for(int row = 0; row < rows; row++) {\n            for(int col = 0; col < cols; col++) {\n                if (row == 0) {\n                    rowHeights[row][col] = matrix[row][col] - \'0\';\n                } else {\n                    if (matrix[row][col] == \'0\') rowHeights[row][col] = 0;\n                    else rowHeights[row][col] = 1 + rowHeights[row-1][col];\n                }\n            }\n        }\n        \n        int maxRectangle = 0;\n        \n        for(auto &heights: rowHeights) {\n            int area = getMaxArea(heights);\n            maxRectangle = max(area, maxRectangle);\n        }\n        \n        return maxRectangle;\n    }\n    \n    // return the maximum area of rectangle in histogram\n    int getMaxArea(vector<int> &heights) {\n        int n = heights.size();\n        vector<int> areas(n);\n        stack<int> stk;\n        stk.push(n);\n        \n        // nearest smaller element to right\n        for(int i = n-1; i >= 0; i--) {\n            int height = heights[i];\n\n            while (stk.top() != n && heights[stk.top()] >= height) stk.pop();\n            \n            areas[i] = stk.top();\n            \n            stk.push(i);\n        }\n\n        stk.push(-1);\n        // nearest smaller element to left\n        for(int i = 0; i < n; i++) {\n            int height = heights[i];\n\n            while (stk.top() != -1 && heights[stk.top()] >= height) stk.pop();\n            \n            // width = right - left - 1\n            // width = right - (left + 1)\n            areas[i] -= stk.top() + 1;\n\n            areas[i] *= height;\n            \n            stk.push(i);\n        }\n        \n        return *max_element(areas.begin(), areas.end());\n    }\n};\n```
['Dynamic Programming', 'Stack', 'Monotonic Stack']