The Stock Span Problem | C # linear time solution for stock span problem ; a linear time solution for stock span problem A stack based efficient method to calculate stock span values ; Create a stack and Push index of first element to it ; Span value of first element is always 1 ; Calculate span values for rest of the elements ; Pop elements from stack while 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 price [ i ] is greater than elements after top of stack ; Push this element to stack ; A utility function to print elements of array ; Driver method ; Fill the span values in array S [ ] ; print the calculated span values
using System ; using System . Collections ; class GFG { static void calculateSpan ( int [ ] price , int n , int [ ] S ) { Stack st = new Stack ( ) ; st . Push ( 0 ) ; S [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { while ( st . Count > 0 && price [ ( int ) st . Peek ( ) ] <= price [ i ] ) st . Pop ( ) ; S [ i ] = ( st . Count == 0 ) ? ( i + 1 ) : ( i - ( int ) st . Peek ( ) ) ; st . Push ( i ) ; } } static void printArray ( int [ ] arr ) { for ( int i = 0 ; i < arr . Length ; i ++ ) Console . Write ( arr [ i ] + " ▁ " ) ; } public static void Main ( String [ ] args ) { int [ ] price = { 10 , 4 , 5 , 90 , 120 , 80 } ; int n = price . Length ; int [ ] S = new int [ n ] ; calculateSpan ( price , n , S ) ; printArray ( S ) ; } }