Largest Rectangle in Histogram

#One pass soln
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        heights.append(-1)
        st = [-1]
        for i, x in enumerate(heights):
            while x < heights[st[-1]]:
                res = max(res, heights[st.pop()]*(i-st[-1]-1))
            st.append(i)
        return res

#multiple pass soln
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)

        #previous smallest element problem
        st = []
        prevs = [-1]*n
        for i, e in enumerate(heights):
            while st and heights[st[-1]] >= e:
                st.pop()
            if st:
                prevs[i] = st[-1]
            st.append(i)

        #next smallest element problem
        st.clear()
        nxts = [n]*n
        for i, e in enumerate(heights):
            while st and heights[st[-1]] >= e:
                nxts[st.pop()] = i
            st.append(i)

        res = 0
        for i,x in enumerate(heights):
            res = max(res, (nxts[i]-prevs[i]-1)*x)
        return res