Simple Solution using Monotonic Stack | C++ | With Diagram Explaination ✅
Better to solve https://leetcode.com/problems/largest-rectangle-in-histogram first.\n\nApproach\n\n1. Initialize: Start by creating a histogram array with one e
Better to solve `https://leetcode.com/problems/largest-rectangle-in-histogram` first.\n\n**Approach**\n\n1. **Initialize**: Start by creating a histogram array with one extra element initialized to 0. This extra element acts as a sentinel.\n2. **Iterate Through Rows**: Traverse each row of the matrix.\n3. **Update Histogram**: For each row, update the histogram by incrementing the height if the corresponding element in the matrix is \'1\', otherwise reset it to 0.\n4. **Calculate Maximum Rectangle Area**: Utilize a monotonic stack to find the maximum area of rectangles. For each histogram bar, if it\'s smaller than the top of the stack, pop the stack and calculate the area using the popped element as height and the difference between the current position and the previous popped element\'s position as width. Update the maximum area accordingly.\n5. **Return Maximum Area**: After processing all rows, return the maximum area found.\n\n<br/><br/>\n\n##### For Row = 1, the maximum area is 1\n<img src="https://assets.leetcode.com/users/images/28767c2e-7d14-492e-8405-a275050831cf_1713010966.420261.png" alt="closed_paren" title="Closed Parenthesis" width="250"/>\n\n<br/><br/>\n\n##### For Row = 2, the maximum area is 3\n<img src="https://assets.leetcode.com/users/images/e492b807-1c94-4490-aa52-d205f8678293_1713011208.7472572.png" alt="closed_paren" title="Closed Parenthesis" width="250"/>\n\n<br/><br/>\n\n##### For Row = 3, the maximum area is 6\n<img src="https://assets.leetcode.com/users/images/d5016a31-b5d3-43af-a22f-c0b98d3db28f_1713011245.4743698.png" alt="closed_paren" title="Closed Parenthesis" width="250"/>\n\n<br/><br/>\n\n##### For Row = 4, the maximum area is 4\n<img src="https://assets.leetcode.com/users/images/348cb5b6-c124-4b32-bd69-8a1b01f4b2cb_1713011254.0632894.png" alt="closed_paren" title="Closed Parenthesis" width="250"/>\n\n\n<br/><br/>\n## Implementation\n\n```\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int maxArea = 0;\n        \n        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;\n        int cols = matrix[0].size();\n        int rows = matrix.size();\n        vector<int>histogram(cols+1, 0);\n        histogram[cols] = -1;\n        stack<pair<int,int>>monotonic;\n        \n        for(auto row: matrix) {\n            for(int i = 0; i < cols; i++) {\n                if(row[i] == \'1\') {\n                    histogram[i]++;\n                } else {\n                    histogram[i] = 0;\n                } \n            }\n            \n            for(int i = 0; i < cols+1; i++) {\n                int x = 0;\n                while(!monotonic.empty() && monotonic.top().first >= histogram[i]) {\n                    auto tp = monotonic.top();  monotonic.pop();\n                    int h = tp.first, steps = tp.second;\n                    x += steps;\n                    maxArea = max(maxArea, h*x);\n                }\n                monotonic.push({histogram[i], x+1});\n            }\n        }\n        \n        return maxArea;\n    }\n};\n```
['Array', 'C', 'Matrix', 'Monotonic Stack', 'C++']