4ms Java solution, using O(n) stack space, O(n) time
public class Solution {\n        public int largestRectangleArea(int[] height) {\n            if ((height == null) || (height.length == 0)) return 0;\n         
    public class Solution {\n        public int largestRectangleArea(int[] height) {\n            if ((height == null) || (height.length == 0)) return 0;\n            final int N = height.length;\n            int[] s = new int[N + 1];\n            int i, top = 0, hi, area = 0;\n            s[0] = -1;\n            for (i = 0; i < N; i++) {\n                hi = height[i];\n                while ((top > 0) && (height[s[top]] > hi)) {\n                    area = Math.max(area, height[s[top]] * (i - s[top - 1] - 1));\n                    top--;\n                }\n                s[++top] = i;\n            }\n            while (top > 0) {\n                area = Math.max(area, height[s[top]] * (N - s[top -1] - 1));\n                top--;\n            }\n            return area;\n        }\n    }
['Stack', 'Java']