Python3 and C++ || Largest Rectangle in Histogram Concept || Simple and Optimal
\n# Code\nPython3 []\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        stack = []\n        maxArea = 0\n        heights.
> ![image.png](https://assets.leetcode.com/users/images/7be15a5e-9dad-4077-99ac-9b825883b1ed_1712985326.6452856.png)\n# Code\n```Python3 []\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        stack = []\n        maxArea = 0\n        heights.append(0)\n        for i, h in enumerate(heights):\n            start = i\n            while stack and stack[-1][1] > h:\n                idx, height = stack.pop()\n                maxArea = max(maxArea, height * (i - idx))\n                start = idx\n            stack.append((start, h))\n        return maxArea\n\n    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n        maxArea = 0\n        height = [0] * len(matrix[0])\n        for i in range(len(matrix)):\n            for j in range(len(matrix[0])):\n                if matrix[i][j] == \'1\':\n                    height[j] += 1\n                else:\n                    height[j] = 0\n            area = self.largestRectangleArea(height)\n            maxArea = max(maxArea, area)\n        return maxArea\n```\n```C++ []\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        stack <pair <int, int>> st;\n        heights.push_back(0);\n        int maxArea = 0;\n        for (int i = 0; i < heights.size(); i++) {\n            int start = i;\n            while (!st.empty() && st.top().second > heights[i]) {\n                auto [idx, height] = st.top();\n                st.pop();\n                maxArea = max(maxArea, height * (i - idx));\n                start = idx;\n            }\n            st.push({start, heights[i]});\n        }\n        return maxArea;\n    }\n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int maxArea = 0;\n        vector <int> height(matrix[0].size(), 0);\n        for (int i = 0; i < matrix.size(); i++) {\n            for (int j = 0; j < matrix[0].size(); j++) {\n                if (matrix[i][j] == \'1\') height[j]++;\n                else height[j] = 0;\n            }\n            int area = largestRectangleArea(height);\n            maxArea = max(maxArea, area);\n        }\n        return maxArea;\n    }\n};\n```
['Array', 'Stack', 'Monotonic Stack', 'C++', 'Python3']