Java | Stack | Detailed Explanation | O(N)
\nIntuition :\n1) Max area will always have atleast one full height on any index\n2) Find largest rectangle including each bar one by one.\n\ta) For each bar, W
```\nIntuition :\n1) Max area will always have atleast one full height on any index\n2) Find largest rectangle including each bar one by one.\n\ta) For each bar, We have to find it\'s left limit & right limit (to know the maximum width)\n\tb) Find each index\'s left limit and store it in left array\n\t\ti) Traverse left to right, try to maximize the width in left side and we will expand until we find prev index\'s val is smaller than curr index\'s val\n\t\tii) We are using stack to check how much we can expand in left side for curr index to find the left limit.\n\t\tiii) Stack will check with the previous value to get to know the left limit but we are traversing right in loop\n\tc) Find it\'s right limit (where we find any index\'s value is smaller than current index in right side array of curr index\n\t\ti) Traverse right to left, try to maximize the width in right side with the help of stack & expand until we find prev index\'s val is smaller.\n\t\tii) Using stack to check how much we can expand in right side for curr index to find the right limit.\n3) Take the maximum of all the max area found by each bar.\n4) calculate area\n\t\twidth * height\nwhere \nwidth = right limit - left limit + 1\nheight = curr index\'s value\n5) Update max area & return it\n```\n```\n    public int largestRectangleArea(int[] heights) {\n        int len = heights.length;\n        int[] left = new int[len];\n        int[] right = new int[len];\n        Stack<Integer> stack = new Stack<>();\n        //traversing left to right and finding the left limit of each number with the help of stack\n        for(int i=0;i<len;i++){\n            if(stack.isEmpty()){\n                stack.push(i);\n                left[i] = 0;\n            }else{\n                //remove the index from stack if their height is greater or equal to curr number\'s height\n                while(!stack.isEmpty() && heights[stack.peek()] >= heights[i])\n                    stack.pop();\n                //when we found the index with less height that becomes left limit of curr number (index+1)\n                left[i] = stack.isEmpty()?0:stack.peek()+1;\n                stack.push(i);\n            }\n        }\n        //removed old stored values\n        stack = new Stack<>();\n        \n        //traversing from right to left and finding the right limit of each number with the help of stack\n        for(int i=len-1;i>=0;i--){\n            if(stack.isEmpty()){\n                stack.push(i);\n                right[i] = len-1;\n            }else{\n                //remove the index from stack if their height is greater or equal to curr number\'s height\n                while(!stack.isEmpty() && heights[stack.peek()] >= heights[i])\n                    stack.pop();\n                //when we found the index with less height that becomes right limit of curr number (index-1)\n                right[i] = stack.isEmpty()?len-1:stack.peek()-1;\n                stack.push(i);\n            }\n        }\n        //calculating the area and finding max area\n        int maxArea = Integer.MIN_VALUE;\n        int[] area = new int[len];\n        for(int i=0;i<len;i++){\n            area[i] = (right[i] - left[i] + 1) * heights[i];\n            maxArea = Math.max(maxArea, area[i]);\n        }\n        return maxArea;\n    }\n```
['Stack', 'Java']