Lecture 157:-Online Stock Span

The Online Stock Span problem involves calculating the span of a stock's price on each day, given a series of daily stock prices. The span of a stock's price on a particular day is defined as the maximum number of consecutive days (including the current day) before the current day, for which the price of the stock was less than or equal to the price on the current day.

To solve this problem, you can use a stack to keep track of the previous days' prices and their spans. When processing a new day's price, you can compare it with the previous days' prices in the stack and calculate the span.

Here's a C++ implementation of the Online Stock Span problem:

cppCopy code

#include <iostream> #include <stack> #include <vector> class StockSpanner { private: std::stack<std::pair<int, int>> prices; // Pair of (price, span) public: StockSpanner() {} int next(int price) { int span = 1; // Minimum span is always 1 (itself) // Pop days whose prices are less than or equal to the current day's price while (!prices.empty() && prices.top().first <= price) { span += prices.top().second; prices.pop(); } // Push the current day's price and its span onto the stack prices.push({price, span}); return span; } }; int main() { StockSpanner spanner; std::vector<int> prices = {100, 80, 60, 70, 60, 75, 85}; for (int price : prices) { int span = spanner.next(price); std::cout << "Span for price " << price << ": " << span << std::endl; } return 0; }

In this implementation, the StockSpanner class maintains a stack of pairs, where each pair represents a day's price and its corresponding span. The next method is used to calculate the span for the next day's price. It pops previous days from the stack as long as their prices are less than or equal to the current day's price, and then pushes the current day's price and its calculated span onto the stack.

For the given example input [100, 80, 60, 70, 60, 75, 85], the output will be:

lessCopy code

Span for price 100: 1 Span for price 80: 1 Span for price 60: 1 Span for price 70: 2 Span for price 60: 1 Span for price 75: 4 Span for price 85: 6

This indicates that the stock span for each day's price. The span values are calculated as described earlier.