Most optimized Code in Java 💯
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int n = heights.length;\n        int max = 0;\n        int nr[] = new int[n];\n        int nl[] = new int[n];\n\n        Stack<Integer> s = new Stack<>();\n        // Right\n        for(int i = n-1; i>=0; i--){\n            while(!s.empty() && heights[s.peek()]>=heights[i]){\n                s.pop();\n            }\n            if(s.empty()){\n                nr[i] = n;\n            }\n            else{\n                nr[i] = s.peek();\n            }\n            s.push(i);\n        }\n        // Left\n        s = new Stack<>();\n        for(int i = 0; i<heights.length; i++){\n            while(!s.empty() && heights[s.peek()]>=heights[i]){\n                s.pop();\n            }\n            if(s.empty()){\n                nl[i] = -1;\n            }\n            else{\n                nl[i] = s.peek();\n            }\n            s.push(i);\n        }\n\n        for(int i = 0; i<n; i++){\n            int hi = heights[i];\n            int width = nr[i]-nl[i]-1;\n            int curr = hi * width;\n            max = Math.max(curr, max);\n        }\n        return max;\n    }\n}\n```
['Java']