The Stock Span Problem | A stack based efficient method to calculate s ; Create a stack and push index of fist element to it ; Span value of first element is always 1 ; Calculate span values for rest of the elements ; Pop elements from stack whlie stack is not empty and top of stack is smaller than price [ i ] ; If stack becomes empty , then price [ i ] is greater than all elements on left of it , i . e . price [ 0 ] , price [ 1 ] , . . price [ i - 1 ] . Else the price [ i ] is greater than elements after top of stack ; Push this element to stack ; A utility function to print elements of array ; Driver program to test above function ; Fill the span values in array S [ ] ; Print the calculated span values
def calculateSpan ( price , S ) : NEW_LINE INDENT n = len ( price ) NEW_LINE st = [ ] NEW_LINE st . append ( 0 ) NEW_LINE S [ 0 ] = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT while ( len ( st ) > 0 and price [ st [ - 1 ] ] <= price [ i ] ) : NEW_LINE INDENT st . pop ( ) NEW_LINE DEDENT S [ i ] = i + 1 if len ( st ) <= 0 else ( i - st [ - 1 ] ) NEW_LINE st . append ( i ) NEW_LINE DEDENT DEDENT def printArray ( arr , n ) : NEW_LINE INDENT for i in range ( 0 , n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT price = [ 10 , 4 , 5 , 90 , 120 , 80 ] NEW_LINE S = [ 0 for i in range ( len ( price ) + 1 ) ] NEW_LINE calculateSpan ( price , S ) NEW_LINE printArray ( S , len ( price ) ) NEW_LINE