C++ Problem

The stock span problem is a financial problem where we have aseries of n daily price quotes for a stock and we need to calculatespan of stock’s price for all n days. The span Si of the stock’sprice on a given day i is defined as the maximum number ofconsecutive days just before the given day, for which the price ofthe stock on the current day is less than or equal to its price onthe given day. For example, if an array of 7 days prices is givenas {100, 80, 60, 70, 60, 75, 85}, then the span values forcorresponding 7 days are {1, 1, 1, 2, 1, 4, 6}

One solution for solving this problem is to traverse the inputprice array. For every element being visited, traverse elements onleft of it and increment the span value of it while elements on theleft side are smaller.This solution runs in O(n^2).

Your job is to write a program that solves this in O(n).To do souse the following algorithm:
We will use stack to store last highest price found till currentindex 

 Now create stack and push 0 in it 

 Create prices array Sto hold Si and put S[0] = 1, because it will be always true Iterate given array from 1 to n (here n = array.length)  If prices[stack.top] <= prices[i] then 

 stack.pop 

 Repeat tillstack is not empty or above condition does not break. 

 Now at thispoint there could be two possible states of stack 

Case 1: Whenstack is empty that means, all previous prices was smaller than current prices ? Case 2: When stack is not empty that means, thereis atleast one price which higher than current prices. 

 If stackis empty then 

 S[i] = i + 1 Else 

 S[i] = i – stack.top 

stack.push(i)