Largest rectangle area in histogram

#better go with method 2 than method 1
#Method 1:
'''
The idea is to use a monotonic stack. We iterate over bars and add them to the stack as long as the last element in the stack is less than the current bar. When the condition doesn't hold, we start to calculate areas by popping out bars from the stack until the last element of the stack is greater than the current. The area is calculated as the number of pops multiplied by the height of the popped bar. On every pop, the height of the bar will be less or equal to the previous (since elements in the stack are always monotonically increasing).

Now let's consider this example [2,1,2]. For this case the formula for the area (number of pops * current height) won't work because when we reach 1 we will pop out 2 from the stack and will not consider it later which is wrong since the largest area here is equal to 3 * 1, i.e we somehow need to remember the previously discarded bars that still can form areas. We solve this problem by storing in the stack the width of the bar as well. So for our example, after discarding 2, we push to the stack the 1 with the width equal to 2.

Time: O(n) - In the worst case we have 2 scans: one for the bars and one for the stack
Space: O(n) - in the wors case we push to the stack the whjole input array

Runtime: 932 ms, faster than 51.27% of Python3 online submissions for Largest Rectangle in Histogram.
Memory Usage: 28.4 MB, less than 30.61% of Python3 online submissions for Largest Rectangle in Histogram
'''

def largestRectangleArea(self, bars: List[int]) -> int:
    st, res = [], 0
    for bar in bars + [-1]: # add -1 to have an additional iteration
        step = 0
        while st and st[-1][1] >= bar:
            w, h = st.pop()
            step += w
            res = max(res, step * h)
#ans=max(mat[i][0]-dp[i][0],ans)
    ```
        st.append((step + 1, bar))

    return res
#Method 2:
#in this method when ever a new element breaks montonic stand we have to pop all elements till  monotonic stack
#become valid and then push the element with last popped index so that it can cover perfectly its window for caluculating i,e. it can also extend the possibility of making rectangle through left of current index by doing this bit change.
class Solution:
    def largestRectangleArea(self, nums: List[int]) -> int:
        ans=0
        q=deque()
        n=len(nums)
        for i,j in enumerate(nums):
            newStart=i
            while q and q[-1][0]>j:
                h,ind=q.pop()
                newStart=ind
                ans=max(ans,h*(i-ind))
            q.append((j,newStart))
        #print(q)
        while q:
            h,ind=q.pop()
            print(h*(n-ind))
            ans=max(ans,h*(n-ind))
        return ans
#Method 3(short):
#Find left immediate max and right immediate max for every element
#now iterate over array and use above info find area of max rectangle
class Solution:
    def maximalRectangle(self, g: List[List[str]]) -> int:
        def find(a):
            q=deque()
            n=len(a)
            pre,pos=[-1]*n,[n]*n#To avoid length=(r-l+1) and make length=(r-l) we decremented and  incremented pre pos vals from 0,n to -1,n-1
            for i,val in enumerate(a):
                while q and a[q[-1]]>=val:#Top>=cur---> increasing stack
                    idx=q.pop()
                    pos[idx]=i
                if q:
                    pre[i]=q[-1]
                q.append(i)
            ans=0
            for i in range(n):
                ans=max(ans,a[i]*(pos[i]-pre[i]-1))#Since here current index is counted twice in both pos and pre
            return ans
        m,n=len(g),len(g[0])
        a=[0]*n
        ans=0
        for i in range(m):
            for j in range(n):
                a[j]=(a[j]+1 if g[i][j]=='1' else 0)
            ans=max(ans,find(a))
        return ans

#Method 3:
class Solution:
    def largestRectangleArea(self, arr: List[int]) -> int:
        n=len(arr)
        def find_left():
            st=[]
            left=[0]*n
            for i in range(n):
                if not st:
                    st.append(i)
                elif arr[st[-1]]<arr[i]:
                    left[i]=st[-1]+1
                    st.append(i)
                else:
                    while st and arr[st[-1]]>=arr[i]:
                        st.pop()
                    if st:
                        left[i]=st[-1]+1
                    st.append(i)
            return left

        def find_right():
            st=[]
            right=[n-1]*n
            for i in range(n):
                if not st or arr[st[-1]]<=arr[i]:
                    st.append(i)
                else:
                    while  st and arr[st[-1]]>arr[i]:
                        right[st.pop()]=i-1
                    st.append(i)
            return right
        right,left=find_right(),find_left()

        area=0
        for i in range(n):
            r,l,h=right[i],left[i],arr[i]
            area=max(area,(r-l+1)*h)
        return area