Java | TC: O(N) | SC: O(N) | Optimal Stack solution
java\n/**\n * Using stack to save the increasing height index.\n *\n * Time Complexity: O(N) --> Each element is visited maximum twice. (Once pushed\n * in stac
```java\n/**\n * Using stack to save the increasing height index.\n *\n * Time Complexity: O(N) --> Each element is visited maximum twice. (Once pushed\n * in stack and once popped for stack)\n *\n * Space Complexity: O(N)\n *\n * N = Length of the input array.\n */\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        if (heights == null) {\n            throw new IllegalArgumentException("Input array is null");\n        }\n\n        int len = heights.length;\n        if (len == 0) {\n            return 0;\n        }\n        if (len == 1) {\n            return heights[0];\n        }\n\n        Deque<Integer> stack = new ArrayDeque<>();\n        int maxArea = 0;\n\n        for (int i = 0; i <= len; i++) {\n            while (!stack.isEmpty() && (i == len || heights[stack.peek()] >= heights[i])) {\n                int h = heights[stack.pop()];\n                int left = stack.isEmpty() ? -1 : stack.peek();\n                /**\n                 * i-1 - left ==> This is calculating the width of the rectangle. Both ith and\n                 * left positions are excluded.\n                 */\n                maxArea = Math.max(maxArea, (i - 1 - left) * h);\n            }\n            stack.push(i);\n        }\n\n        return maxArea;\n    }\n}\n```\n\n---\n\nSolutions to other similar question on LeetCode:\n- [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/discuss/1519263/Java-or-TC:-O(RC)-or-SC:-O(min(RC))-or-Optimal-Stack-solution)\n
['Array', 'Stack', 'Java']