C++/Java/Python/JavaScript || ✅🚀 Stack || ✔️🔥TC : O(n)
Intuition:\nThe intuition behind the solution is to use two arrays, nsr (nearest smaller to the right) and nsl (nearest smaller to the left), to determine the b
# Intuition:\nThe intuition behind the solution is to use two arrays, `nsr` (nearest smaller to the right) and `nsl` (nearest smaller to the left), to determine the boundaries of the rectangle for each bar in the histogram. By calculating the area for each rectangle and keeping track of the maximum area, we can find the largest rectangle in the histogram.\n\n# Approach:\n1. Initialize an empty stack `s` to store the indices of the histogram bars.\n2. Create two arrays, `nsr` and `nsl`, each of size `n` (where `n` is the number of elements in the `heights` vector), and initialize all elements to 0.\n3. Process the histogram bars from right to left:\n   - While the stack is not empty and the height of the current bar is less than or equal to the height of the bar at the top of the stack, pop the stack.\n   - If the stack becomes empty, set `nsr[i]` (the nearest smaller to the right for the current bar) to `n`.\n   - Otherwise, set `nsr[i]` to the index at the top of the stack.\n   - Push the current index `i` onto the stack.\n4. Empty the stack.\n5. Process the histogram bars from left to right:\n   - While the stack is not empty and the height of the current bar is less than or equal to the height of the bar at the top of the stack, pop the stack.\n   - If the stack becomes empty, set `nsl[i]` (the nearest smaller to the left for the current bar) to -1.\n   - Otherwise, set `nsl[i]` to the index at the top of the stack.\n   - Push the current index `i` onto the stack.\n6. Initialize a variable `ans` to 0. This variable will store the maximum rectangle area.\n7. Iterate over the histogram bars:\n   - Calculate the area of the rectangle for the current bar using the formula: `heights[i] * (nsr[i] - nsl[i] - 1)`.\n   - Update `ans` with the maximum of `ans` and the calculated area.\n8. Return `ans` as the largest rectangle area in the histogram.\n\n# Complexity:\n- The time complexity of this solution is O(n), where n is the number of elements in the `heights` vector. This is because each bar is processed only once.\n- The space complexity is O(n) as well because we use two additional arrays of size n, `nsr` and `nsl`, and a stack to store indices.\n\n---\n# C++\n```cpp\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights){\n        int n=heights.size();\n        vector<int> nsr(n,0);\n        vector<int> nsl(n,0);\n\n        stack<int> s;\n\n        for(int i=n-1;i>=0;i--){\n            while(!s.empty() && heights[i]<=heights[s.top()]){\n                s.pop();\n            }\n            if(s.empty()) nsr[i]=n;\n            else nsr[i]=s.top();\n            s.push(i);\n        }\n\n        while(!s.empty()) s.pop();\n\n        for(int i=0;i<n;i++){\n            while(!s.empty() && heights[i]<=heights[s.top()]){\n                s.pop();\n            }\n            if(s.empty()) nsl[i]=-1;\n            else nsl[i]=s.top();\n            s.push(i);\n        }\n\n        int ans=0;\n\n        for(int i=0;i<n;i++){\n            ans=max(ans, heights[i]*(nsr[i]-nsl[i]-1));\n        }\n        return ans;        \n    }\n};\n```\n\n---\n# JAVA\n```java\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int n = heights.length;\n        int[] nsr = new int[n];\n        int[] nsl = new int[n];\n        \n        Stack<Integer> s = new Stack<>();\n\n        for (int i = n - 1; i >= 0; i--) {\n            while (!s.isEmpty() && heights[i] <= heights[s.peek()]) {\n                s.pop();\n            }\n            if (s.isEmpty()) nsr[i] = n;\n            else nsr[i] = s.peek();\n            s.push(i);\n        }\n\n        while (!s.isEmpty()) s.pop();\n\n        for (int i = 0; i < n; i++) {\n            while (!s.isEmpty() && heights[i] <= heights[s.peek()]) {\n                s.pop();\n            }\n            if (s.isEmpty()) nsl[i] = -1;\n            else nsl[i] = s.peek();\n            s.push(i);\n        }\n\n        int ans = 0;\n\n        for (int i = 0; i < n; i++) {\n            ans = Math.max(ans, heights[i] * (nsr[i] - nsl[i] - 1));\n        }\n        return ans;\n    }\n}\n```\n\n---\n\n# Python\n```py\nclass Solution(object):\n    def largestRectangleArea(self, heights):\n        n = len(heights)\n        nsr = [0] * n\n        nsl = [0] * n\n\n        s = []\n\n        for i in range(n - 1, -1, -1):\n            while s and heights[i] <= heights[s[-1]]:\n                s.pop()\n            if not s:\n                nsr[i] = n\n            else:\n                nsr[i] = s[-1]\n            s.append(i)\n\n        while s:\n            s.pop()\n\n        for i in range(n):\n            while s and heights[i] <= heights[s[-1]]:\n                s.pop()\n            if not s:\n                nsl[i] = -1\n            else:\n                nsl[i] = s[-1]\n            s.append(i)\n\n        ans = 0\n\n        for i in range(n):\n            ans = max(ans, heights[i] * (nsr[i] - nsl[i] - 1))\n        return ans\n\n```\n\n---\n\n# JavaScript\n```js\nvar largestRectangleArea = function(heights) {\n    const n = heights.length;\n    const nsr = new Array(n).fill(0);\n    const nsl = new Array(n).fill(0);\n\n    const stack = [];\n        \n    for (let i = n - 1; i >= 0; i--) {\n        while (stack.length !== 0 && heights[i] <= heights[stack[stack.length - 1]]) {\n                stack.pop();\n        }\n        if (stack.length === 0) {\n            nsr[i] = n;\n        } else {\n            nsr[i] = stack[stack.length - 1];\n        }\n        stack.push(i);\n    }\n\n    while (stack.length !== 0) {\n        stack.pop();\n    }\n\n    for (let i = 0; i < n; i++) {\n        while (stack.length !== 0 && heights[i] <= heights[stack[stack.length - 1]]) {\n            stack.pop();\n        }\n        if (stack.length === 0) {\n            nsl[i] = -1;\n        } else {\n             nsl[i] = stack[stack.length - 1];\n        }\n        stack.push(i);\n    }\n\n    let ans = 0;\n\n    for (let i = 0; i < n; i++) {\n        ans = Math.max(ans, heights[i] * (nsr[i] - nsl[i] - 1));\n    }\n   \n    return ans;\n};\n```
['Monotonic Stack', 'Python', 'C++', 'Java', 'JavaScript']