Largest Rectangle in Histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        h.push_back(0);
        stack<int> st;
        int best = 0;
        for (int i = 0; i < (int)h.size(); ++i) {
            while (!st.empty() && h[st.top()] > h[i]) {
                int top = st.top(); st.pop();
                int width = st.empty() ? i : (i - st.top() - 1);
                best = max(best, h[top] * width);
            }
            st.push(i);
        }
        h.pop_back();
        return best;
    }
};

func largestRectangleArea(h []int) int {
    h = append(h, 0)
    st := []int{}
    best := 0
    for i := 0; i < len(h); i++ {
        for len(st) > 0 && h[st[len(st)-1]] > h[i] {
            top := st[len(st)-1]
            st = st[:len(st)-1]
            width := i
            if len(st) > 0 {
                width = i - st[len(st)-1] - 1
            }
            if area := h[top] * width; area > best {
                best = area
            }
        }
        st = append(st, i)
    }
    return best
}

from typing import List

class Solution:
    def largestRectangleArea(self, h: List[int]) -> int:
        h.append(0)
        st: List[int] = []
        best = 0
        for i in range(len(h)):
            while st and h[st[-1]] > h[i]:
                top = st.pop()
                width = i if not st else i - st[-1] - 1
                best = max(best, h[top] * width)
            st.append(i)
        h.pop()
        return best

function largestRectangleArea(h) {
    h.push(0);
    const st = [];
    let best = 0;
    for (let i = 0; i < h.length; i++) {
        while (st.length > 0 && h[st[st.length - 1]] > h[i]) {
            const top = st.pop();
            const width = st.length === 0 ? i : i - st[st.length - 1] - 1;
            best = Math.max(best, h[top] * width);
        }
        st.push(i);
    }
    h.pop();
    return best;
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] h = new int[n + 1];
        System.arraycopy(heights, 0, h, 0, n);
        h[n] = 0;
        Deque<Integer> st = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i < h.length; i++) {
            while (!st.isEmpty() && h[st.peek()] > h[i]) {
                int top = st.pop();
                int width = st.isEmpty() ? i : (i - st.peek() - 1);
                best = Math.max(best, h[top] * width);
            }
            st.push(i);
        }
        return best;
    }
}

function largestRectangleArea(h: number[]): number {
    h.push(0);
    const st: number[] = [];
    let best = 0;
    for (let i = 0; i < h.length; i++) {
        while (st.length > 0 && h[st[st.length - 1]] > h[i]) {
            const top = st.pop() as number;
            const width = st.length === 0 ? i : i - st[st.length - 1] - 1;
            best = Math.max(best, h[top] * width);
        }
        st.push(i);
    }
    h.pop();
    return best;
}