The Stock Span Problem | C ++ 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 program to test above function ; Fill the span values in array S [ ] ; print the calculated span values
#include <iostream> NEW_LINE #include <stack> NEW_LINE using namespace std ; void calculateSpan ( int price [ ] , int n , int S [ ] ) { stack < int > st ; st . push ( 0 ) ; S [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { while ( ! st . empty ( ) && price [ st . top ( ) ] <= price [ i ] ) st . pop ( ) ; S [ i ] = ( st . empty ( ) ) ? ( i + 1 ) : ( i - st . top ( ) ) ; st . push ( i ) ; } } void printArray ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int price [ ] = { 10 , 4 , 5 , 90 , 120 , 80 } ; int n = sizeof ( price ) / sizeof ( price [ 0 ] ) ; int S [ n ] ; calculateSpan ( price , n , S ) ; printArray ( S , n ) ; return 0 ; }