Largest Rectangle in Histogram

Learn Nearest Smaller to Left and Nearest Smaller to Right for this

Problem Link: https://leetcode.com/problems/largest-rectangle-in-histogram/

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        
        nsl=[]
        nsr=[]
        n=len(heights)
        
        # NSL
        s=[]
        for i in range(n):
            if(len(s)==0):
                nsl.append(-1)
            else:
                if(heights[s[-1]]<heights[i]):
                    nsl.append(s[-1])
                else:
                    while(len(s)>0 and heights[s[-1]]>=heights[i]):
                        s.pop()
                    
                    if(len(s)==0):
                        nsl.append(-1)
                    else:
                        nsl.append(s[-1])
            
            s.append(i)
        
        # NSR
        s=[]
        for i in range(n-1,-1,-1):
            if(len(s)==0):
                nsr.append(n)
            else:
                if(heights[s[-1]]<heights[i]):
                    nsr.append(s[-1])
                else:
                    while(len(s)>0 and heights[s[-1]]>=heights[i]):
                        s.pop()
                    
                    if(len(s)==0):
                        nsr.append(n)
                    else:
                        nsr.append(s[-1])
            s.append(i)
        nsr=nsr[::-1]
        
        print(nsl)
        print(nsr)
        ans=0
        for i in range(n):
            ans=max(ans, (nsr[i]-nsl[i]-1)*heights[i])
        
        return ans