Maximum ractangular area in a histogram

'''
Logic:
M-1: T.C : O(n) S.C : O(n) : 3 pass
Basically we will find the left first min and right first min using stack and then again traversing the array
and distance between left min to right min multiplied by current element height and update the maximum everytime.

M-2: T.C : O(n) S.C : O(n) : 1 pass
Suppose we are finding the last min using stack of pair where stack first element will be index of current element
and second element will be the index of left minimum element(-1 if there is no such element exists)
Steps:
push first element index with -1 because no element before it and start iterating from first index
Case 1: suppose current top element of stack is smaller than current ith element means for ith element,left minimum is top
element index so push current element in stack as {i,st.top().first}.So if any element is in stack that means it's left
minimum index will also be there as second element.

Case 2: Suppose current top element of stack is greater or equal to current element then first right minimum of top
element will be the current element and stack top element second element denotes the left minimum element index so
now we can calculate the area of histogram of arr[i] height by (right-left-1)*top_element_height so find it and update
every time.

After doing for whole array,find all histogram area which is present in stack as their next minimum is not present in array
so consider n as next right min element and update the answer also.
'''

class Solution:
    def largestRectangleArea(self, arr: List[int]) -> int:
        st = []   # [height, index]
        ans = 0
        n = len(arr)

        for i in range(n):
            while st and arr[i] < st[-1][0]:
                h, idx = st.pop()
                left = st[-1][1] if st else -1
                width = i - left - 1
                ans = max(ans, h * width)
            st.append([arr[i], i])

        while st:
            h, idx = st.pop()
            left = st[-1][1] if st else -1
            width = n - left - 1
            ans = max(ans, h * width)

        return ans

#Just another design
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans=0
        st=[]
        st.append(-1)
        for i in range(len(heights)):
            while len(st)>1 and heights[st[-1]]>heights[i]:
                temp=st.pop()
                ans=max(ans,(i-st[-1]-1)*heights[temp])
            st.append(i)
        n=len(heights)
        while len(st)>1:
            temp=st.pop()
            ans=max(ans,(n-st[-1]-1)*heights[temp])
        return ans