Java: For each building, I verify it's right and left buildings in order to calculate the number of buildings greater or equals current building.

public static long largestRectangle(List h) { // Write your code here int maxArea = 0;

    int nbrBuildings = 1;

    for (int i = 0; i < h.size(); i++) {
        for (int j = i + 1; j < h.size(); j++) {
            if (h.get(i) <= h.get(j)) {
                nbrBuildings++;
            } else {
                break;
            }
        }
        for (int j = i - 1; j >= 0; j--) {
            if (h.get(i) <= h.get(j)) {
                nbrBuildings++;
            } else {
                break;
            }
        }
        maxArea = Math.max(maxArea, nbrBuildings * h.get(i));
        nbrBuildings = 1;
    }

    return maxArea;
}

func largestRectangle(h []int32) int64 {

// since this is a lookup, it should be a stack, as it's a natural choice for skipping lookup values. if we look up behind, we want to skip values that will not be needed anymore. the question is how we'll decide if they are not needed  
    // the formula suggests that we skip Ks 
    // so once next height is lower that on the top of the stack - we start popping values until we meet a lower one (or stack is empty), calculating all possible squares and memorising max value
// rinse and repeat.
    // This logic works because we'll always keep our stack increasing monotonously, and once new value is lower - there's no need in keeping that in the stack, thus we level it, remembering maximum square in the previous state:

    // here's visual interpretation:

//     |        |

    //   | |      | | |.       |   

    // | | | -> | | | | -> |...| where ... are values popped from the stack

    // since we're storing indexes, we still know the width. If there was such a height that resulting square was greater - we've remembered it when popping values
// 
// to flush the stack, add zero to the end
stack := []int32{}
//add finishig element
h = append(h, 0)
result := int64(0)
for i := int32(0); i < int32(len(h)); i++ {
    //if stack is empty, square == height
    if len(stack) == 0 { result = max(result, int64(h[i])) }
    width := int32(0)
    for len(stack) > 0 && h[stack[len(stack)-1]] >= h[i] {
        fmt.Printf("Popping up stack %v\n", stack)
        //pop the stack value
        peekIndex := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        //increase width and calculate square
        if len(stack) == 0 {
            width = i
        } else {
            width = i-stack[len(stack)-1]-1
        }
        sq := int64(h[peekIndex]*width)
        result = max(result, sq)
    }
    stack = append(stack, i)
}
return result

}

I was looking for this thread for my youtube mp3 project. Now finally landed at the right page.

Here's my solution in C++. It's a little messy, but it works alright :)

long largestRectangle(vector<int> h) {

    int largestArea = 0;
    int currentArea = 0;
    int lengthWithH = 0;
    
    for (int i = 0; i < h.size(); i++) // Check each height
    {
        if (i > 0 && h.at(i) == h.at(i - 1)) // if height is same as previous, no need to check
            continue;
            
        lengthWithH = 1; // count self
        bool left = true;
        bool right = true;
        for (int j = 1; j < h.size(); j++)
        {
            if (!left && !right) // if no more to check, break loop
            {
                break;
            }
            if (left)
            {
                if (i - j >= 0 && h.at(i - j) >= h.at(i)) // check if building left is tall enough, and in bounds
                    lengthWithH++;
                else
                    left = false;
            }
            if (right)
            {
                if (i + j < h.size() && h.at(i + j) >= h.at(i)) // check if building right is tall enough, and in bounds
                    lengthWithH++;
                else
                    right = false;
            }
        }
        currentArea = h.at(i) * lengthWithH; // find area
        
        if (currentArea > largestArea) // if new area is larger, set it to largest
            largestArea = currentArea;
    }
    return largestArea;
}

This is one of the hard ones. I watched a YouTube video on how to solve it. And here is my code. It is pretty descriptive IMHO. Easy to read. The key is whenever the height decreases, the previous taller builds effectively reached the end of their lives. And we can calculate their max areas. And we can extend the starting position of the new lower height to the leftest one that is 'killed' by this new lower height. Adding a '0' to the end of the height so that at the end, all the leftover heights are killed by this '0' and we can calculate their max areas.

def largestRectangle(h):

h.append(0)
alive = [[0, h[0]]]
maxArea = 0

for pos, val in enumerate(h):
    if pos == 0:
        continue
    if len(alive)>0 and val < alive[-1][1]:
        while len(alive)>0 and val < alive[-1][1]:
            dead = alive.pop()
            maxArea = max(maxArea, dead[1]*(pos-dead[0]))
            start = dead[0]

        alive.append([start, val])
    else:
        alive.append([pos, val])    
return maxArea