O(N) using single Stack in java
\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        \n        /* Naive Solution \n        \n        int i;\n        int max=height
```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        \n        /* Naive Solution \n        \n        int i;\n        int max=heights[0];\n        for(i=0;i<heights.length;i++)\n        {\n            int sum=heights[i];\n            for(int j=i+1;j<heights.length;j++)\n            {\n                if(heights[j]>=heights[i])\n                    sum+=heights[i];\n                else\n                    break;\n            }\n             for(int j=i-1;j>=0;j--)\n            {\n                if(heights[j]>=heights[i])\n                    sum+=heights[i];\n                 else\n                     break;\n            }\n            \n            max=Math.max(max,sum);\n        }\n        return(max);\n        \n        */\n        \n        int i,n=heights.length;\n        int res=0;\n        int tb,cur;\n        Stack<Integer> s=new Stack<>();\n        \n        for(i=0;i<heights.length;i++)\n        {\n            while(!s.isEmpty()&&heights[s.peek()]>=heights[i])\n            {\n                tb=s.pop();\n                cur=heights[tb]*(s.isEmpty()?i:i-s.peek()-1);\n                res=Math.max(res,cur);\n            }\n            s.push(i);\n        }\n        \n        while(!s.isEmpty())\n        {\n            tb=s.pop();\n                cur=heights[tb]*(s.isEmpty()?n:n-s.peek()-1);\n                res=Math.max(res,cur);\n        }\n        return(res);\n        \n        \n        \n        \n    }\n}\n```
['Stack', 'Java']