Same as LeetCodes "Largest Rectangle in Histogram" https://leetcode.com/problems/largest-rectangle-in-histogram/submissions/1092315461/

    stack = [-1]
    h.append(0)
    maxA = 0
    for i in range(len(h)):
        while h[i] < h[stack[-1]]:
            height = h[stack.pop()]
            width = i - stack[-1] -1
            if height * width > maxA:
                maxA = height * width
        stack.append(i)
    return maxA

Python, recursive, not O(N) but short.

def largestRectangle(h):
    if h:
        i = min(range(len(h)), key=h.__getitem__)
        return max(h[i] * len(h), largestRectangle(h[:i]), largestRectangle(h[i+1:]))
    return 0

def largestRectangle(h): # Write your code here stack = [0] area = 0 top = 0 h.append(0) for i in range(1, len(h)):

    if h[i] >= h[stack[-1]]:
        stack.append(i)

    else:
        while stack and h[i] < h[stack[-1]]:
            last = stack.pop()
            if stack:
                area = (i - stack[-1]-1) * h[last]
            else:
                area = i * h[last]
            if  area > top:
                top = area
        stack.append(i)

return top

Java O(n)

public static long largestRectangle(List<Integer> h) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        int n = h.size();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && h.get(stack.peek()) >= h.get(i)) {
                int height = h.get(stack.pop());
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int height = h.get(stack.pop());
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, (long) height * width);
        }
        return maxArea;
    }

Java 8 Solution:

public static long largestRectangle(List<Integer> h) {
                //1. Iterate the list of height. Set the max height of the building as first element.
                // then check the height difference to the adjacent building.
                // If the height is same or more, then go to next building.
                //Each time find the max rectangle and update the value.
                long maxRectangle = 0L;

                for(int i = 0; i < h.size(); i++){
                        int maxHt = h.get(i);
                        int maxlen = 1;
                        for(int j = i+1; j < h.size(); j++){
                                if(h.get(j) - h.get(j-1) < 0){
                                        if(maxHt > h.get(j))maxHt = h.get(j);
                                }
                                maxlen+= 1;
                                if(maxRectangle < maxHt*maxlen) maxRectangle = maxHt*maxlen;
                        }
                }
                return maxRectangle;
        }