5ms O(n) Java solution explained (beats 96%)
For any bar i the maximum rectangle is of width r - l - 1 where r - is the last coordinate of the bar to the right with height h[r] >= h[i] and l - is the last 
For any bar `i` the maximum rectangle is of width `r - l - 1` where r - is the last coordinate of the bar to the **right** with height `h[r] >= h[i]` and l - is the last coordinate of the bar to the **left** which height `h[l] >= h[i]`\n\nSo if for any `i` coordinate we know his utmost higher (or of the same height) neighbors to the right and to the left, we can easily find the largest rectangle:\n\n    int maxArea = 0;\n    for (int i = 0; i < height.length; i++) {\n        maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));\n    }\n\nThe main trick is how to effectively calculate `lessFromRight` and `lessFromLeft` arrays. The trivial solution is to use **O(n^2)** solution and for each `i` element first find his left/right heighbour in the second inner loop just iterating back or forward:\n\n    for (int i = 1; i < height.length; i++) {              \n        int p = i - 1;\n        while (p >= 0 && height[p] >= height[i]) {\n            p--;\n        }\n        lessFromLeft[i] = p;              \n    }\n\nThe only line change shifts this algorithm from **O(n^2)** to **O(n)** complexity: we don't need to rescan each item to the left - we can reuse results of previous calculations and "jump" through indices in quick manner:\n\n    while (p >= 0 && height[p] >= height[i]) {\n          p = lessFromLeft[p];\n    }\n\nHere is the whole solution:\n\n    public static int largestRectangleArea(int[] height) {\n        if (height == null || height.length == 0) {\n            return 0;\n        }\n        int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current\n        int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current\n        lessFromRight[height.length - 1] = height.length;\n        lessFromLeft[0] = -1;\n\n        for (int i = 1; i < height.length; i++) {\n            int p = i - 1;\n\n            while (p >= 0 && height[p] >= height[i]) {\n                p = lessFromLeft[p];\n            }\n            lessFromLeft[i] = p;\n        }\n\n        for (int i = height.length - 2; i >= 0; i--) {\n            int p = i + 1;\n\n            while (p < height.length && height[p] >= height[i]) {\n                p = lessFromRight[p];\n            }\n            lessFromRight[i] = p;\n        }\n\n        int maxArea = 0;\n        for (int i = 0; i < height.length; i++) {\n            maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));\n        }\n\n        return maxArea;\n    }
['Dynamic Programming', 'Java']