Detailed explanation with diagrams and examples using pen and paper|| Brute-force and Optimized
Explanation\n\n\n\n\n\n\n\nJAVA Code\n1. Brute force (To understand he concept)\n\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n     
**Explanation**\n\n![image](https://assets.leetcode.com/users/images/2c86f2b6-821c-44d5-8ae4-0f016dfcdf61_1643475595.6156461.jpeg)\n\n![image](https://assets.leetcode.com/users/images/20acec8f-02f2-47ec-9c88-94b88577ad7f_1643475593.3028414.jpeg)\n\n\n\n**JAVA Code**\n1. Brute force (To understand he concept)\n```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int len = heights.length;\n        if(len == 0) return 0;\n        return  helper(heights, len);\n    }\n    private int helper(int height[], int len){\n        //We will check Nearest smallest to the left\n        Stack <Integer> NSL = new Stack <>();\n        //To check Nearest smallest to the right\n        Stack <Integer> NSR = new Stack<>();\n        int left[] = new int[len];\n        int right[] = new int[len];\n        //NSL\n        for(int i = 0; i < len; i++){            \n           if(NSL.isEmpty()) left[i] = -1;\n           else if(!NSL.isEmpty() && height[NSL.peek()] >= height[i]){\n               while(!NSL.isEmpty() && height[NSL.peek()] >= height[i])\n                   NSL.pop();\n               if(NSL.isEmpty()) left[i] = -1;\n               else left[i] = NSL.peek();\n           }else left[i] = NSL.peek();\n           // System.out.print("\\t"  + left[i]); \n           NSL.push(i); \n        }\n        // System.out.print("\\n");\n        //NSR\n        for(int i = len - 1; i >= 0; i--){\n            if(NSR.isEmpty()) right[i] = len;\n            else if(!NSR.isEmpty() && height[NSR.peek()] >= height[i]){\n               while(!NSR.isEmpty() && height[NSR.peek()] >= height[i])\n                   NSR.pop();\n               if(NSR.isEmpty()) right[i] = len;\n               else right[i] = NSR.peek();\n           }else right[i] = NSR.peek();\n           // System.out.print("\\t" + right[i]);  \n           NSR.push(i); \n        }\n       int result = 0;\n//         To find max distance from smallest element from left and smallest to it right\n        for(int i = 0; i < len; i++){\n          result =  Math.max(result, (right[i] - left[i] - 1) * height[i]); \n        }\n        return result;\n    }\n}\n```\n\n2. Optimized\n\n```\n public int largestRectangleArea(int[] heights) {\n        int len = heights.length;\n        Stack<Integer> s = new Stack<>();\n        int maxArea = 0;\n        for (int i = 0; i <= len; i++){\n            int h = (i == len ? 0 : heights[i]);\n            if (s.isEmpty() || h >= heights[s.peek()]) {\n                s.push(i);\n            } else {\n                int top = s.pop();\n                maxArea = Math.max(maxArea, heights[top] * (s.isEmpty() ? i : i - 1 - s.peek()));\n                i--;\n            }\n        }\n        return maxArea;\n    }\n```\n\nNOTE: Try understanding concepts of  Nearest smallest from left/ right && Nearest greatest from left/right for better understanding \n\n<br>\n<br>\n\nString yourReaction;\nif("understood".equals(yourReaction) || "liked it".equals(yourReaction))\nSystem.out.println(**"Please upvote!"**)
['Java']