The Stock Span Problem | Java 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
import java . util . Stack ; import java . util . Arrays ; public class GFG { static void calculateSpan ( int price [ ] , int n , int S [ ] ) { Stack < Integer > st = new Stack < > ( ) ; st . push ( 0 ) ; S [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { while ( ! st . empty ( ) && price [ st . peek ( ) ] <= price [ i ] ) st . pop ( ) ; S [ i ] = ( st . empty ( ) ) ? ( i + 1 ) : ( i - st . peek ( ) ) ; st . push ( i ) ; } } static void printArray ( int arr [ ] ) { System . out . print ( Arrays . toString ( arr ) ) ; } 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 ) ; } }