🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n---\n\n\n---\n# Intuition\nThe problem can be visualized as calculating the largest rectangle that can be formed in a histogram. The intuition is to use a s
![image.png](https://assets.leetcode.com/users/images/adb45702-45b0-4eae-a736-8b972f8edb5e_1733673154.8086953.png)\n\n---\n![1000028614.png](https://assets.leetcode.com/users/images/8640e877-1d52-4a8d-bd2b-2ba3f5adb533_1733675517.6725366.png)\n\n---\n# Intuition\nThe problem can be visualized as calculating the largest rectangle that can be formed in a histogram. The intuition is to use a **stack** to keep track of indices of histogram bars that are not yet resolved. By ensuring that the heights in the stack are in increasing order, we can calculate the largest rectangle for each bar as soon as we encounter a bar of smaller height.\n\n---\n\n# Approach\n1. **Use a stack** to store indices of bars in increasing order of height.\n2. When a bar of smaller height is encountered, **calculate the maximum area** for all indices in the stack that are greater than the current bar\'s height.\n3. Use a **sentinel value** of `0` height at the end to ensure all bars are processed.\n4. For each resolved height, calculate the area using the width determined by the current index and the index of the previous smaller height.\n\n---\n\n# Complexity\n- **Time Complexity**:  \n  $$O(n)$$ because each bar is pushed and popped from the stack at most once.\n\n- **Space Complexity**:  \n  $$O(n)$$ for the stack.\n\n---\n\n\n```python []\nclass Solution:\n    def largestRectangleArea(self, heights):\n        stack = []\n        max_area = 0\n        n = len(heights)\n\n        for i in range(n + 1):\n            current_height = heights[i] if i < n else 0\n\n            while stack and heights[stack[-1]] > current_height:\n                height = heights[stack.pop()]\n                width = i if not stack else i - stack[-1] - 1\n                max_area = max(max_area, height * width)\n            \n            stack.append(i)\n        \n        return max_area\n```\n\n\n```cpp []\n#include <vector>\n#include <stack>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        stack<int> st;\n        int maxArea = 0;\n        int n = heights.size();\n\n        for (int i = 0; i <= n; ++i) {\n            int currentHeight = (i == n) ? 0 : heights[i];\n\n            while (!st.empty() && heights[st.top()] > currentHeight) {\n                int height = heights[st.top()];\n                st.pop();\n                int width = st.empty() ? i : i - st.top() - 1;\n                maxArea = max(maxArea, height * width);\n            }\n\n            st.push(i);\n        }\n\n        return maxArea;\n    }\n};\n```\n\n\n```java []\nimport java.util.Stack;\n\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        Stack<Integer> stack = new Stack<>();\n        int maxArea = 0;\n        int n = heights.length;\n\n        for (int i = 0; i <= n; i++) {\n            int currentHeight = (i == n) ? 0 : heights[i];\n\n            while (!stack.isEmpty() && heights[stack.peek()] > currentHeight) {\n                int height = heights[stack.pop()];\n                int width = stack.isEmpty() ? i : i - stack.peek() - 1;\n                maxArea = Math.max(maxArea, height * width);\n            }\n\n            stack.push(i);\n        }\n\n        return maxArea;\n    }\n}\n```\n\n\n```go []\nfunc largestRectangleArea(heights []int) int {\n    stack := []int{}\n    maxArea := 0\n    n := len(heights)\n\n    for i := 0; i <= n; i++ {\n        currentHeight := 0\n        if i < n {\n            currentHeight = heights[i]\n        }\n\n        for len(stack) > 0 && heights[stack[len(stack)-1]] > currentHeight {\n            height := heights[stack[len(stack)-1]]\n            stack = stack[:len(stack)-1]\n            width := i\n            if len(stack) > 0 {\n                width = i - stack[len(stack)-1] - 1\n            }\n            maxArea = max(maxArea, height*width)\n        }\n\n        stack = append(stack, i)\n    }\n\n    return maxArea\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n\n\n```javascript []\nvar largestRectangleArea = function(heights) {\n    let stack = [];\n    let maxArea = 0;\n    let n = heights.length;\n\n    for (let i = 0; i <= n; i++) {\n        let currentHeight = (i === n) ? 0 : heights[i];\n\n        while (stack.length && heights[stack[stack.length - 1]] > currentHeight) {\n            let height = heights[stack.pop()];\n            let width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;\n            maxArea = Math.max(maxArea, height * width);\n        }\n\n        stack.push(i);\n    }\n\n    return maxArea;\n};\n```\n\n\n```dart []\nclass Solution {\n  int largestRectangleArea(List<int> heights) {\n    int n = heights.length;\n    List<int> stack = [];\n    int maxArea = 0;\n\n    for (int i = 0; i <= n; i++) {\n      int currentHeight = (i == n) ? 0 : heights[i];\n\n      while (stack.isNotEmpty && heights[stack.last] > currentHeight) {\n        int height = heights[stack.removeLast()];\n        int width = stack.isEmpty ? i : i - stack.last - 1;\n        maxArea = max(maxArea, height * width);\n      }\n\n      stack.add(i);\n    }\n\n    return maxArea;\n  }\n}\n```\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Array', 'Stack', 'C', 'Monotonic Stack', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']