Python Solution Using Monotonic Stack With Explanation
Problem Description\n\nThe problem requires finding the area of the largest rectangle that can be formed in a histogram represented by an array of non-negative 
## Problem Description\n\nThe problem requires finding the area of the largest rectangle that can be formed in a histogram represented by an array of non-negative integers `heights`, where each bar\'s width is 1 unit.\n\n## Approach Explanation\n\nThis solution uses a stack-based approach to calculate the maximum rectangle area efficiently:\n- Initialize `max_area` to 0 to keep track of the maximum area encountered.\n- Initialize an empty stack to store indices and corresponding heights.\n- Iterate through each index `i` and height `h` in the `heights` array:\n  - If the stack is empty or the height `h` is greater than or equal to the height at the top of the stack (`stack[-1][1]`):\n    - Push the current index `i` and height `h` onto the stack.\n  - Otherwise, while the stack is not empty and the height at the top of the stack (`stack[-1][1]`) is greater than the current height `h`:\n    - Pop the top of the stack (`idx, he = stack.pop()`).\n    - Calculate the area using the popped height `he` and the difference between the current index `i` and the popped index `idx` (`(i - idx) * he`).\n    - Update `max_area` with the maximum of the current `max_area` and the calculated area.\n- After processing all heights in the `heights` array, handle any remaining heights in the stack to calculate potential areas.\n- Return the `max_area` as the result, which represents the area of the largest rectangle in the histogram.\n\n```python\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        max_area = 0\n        stack = []\n        for i , h in enumerate(heights):\n            idx = i\n            if not stack:\n                stack.append([i , h])\n                continue\n            while stack and stack[-1][1] > h:\n                idx , he = stack.pop()\n                max_area = max(max_area , (i - idx ) * he)\n            stack.append([idx , h])\n\n        while stack:\n            idx , he = stack.pop()\n            max_area = max(max_area , (i - idx + 1) * he) \n        return max_area\n```\n\n## Complexity Analysis\n\n- **Time Complexity**: O(n), where `n` is the number of elements in the `heights` array. Each element is processed a constant number of times (pushed and popped from the stack), resulting in linear time complexity.\n- **Space Complexity**: O(n), where `n` is the number of elements in the `heights` array. The stack can potentially hold all elements in the worst-case scenario (non-decreasing heights).\n---\nYou Should solve this now : [Leetcode 85](https://leetcode.com/problems/maximal-rectangle) [Leetcode 85 Solution](https://leetcode.com/problems/maximal-rectangle/solutions/5015357/python-solution-using-previous-technique-clearly-explained/)\n> #### ***If You Found it helpful, please upvote it. Thanks***\n![Image](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)\n\n
['Stack', 'Monotonic Stack', 'Python3']