Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.
The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today's price.
7 days were [100,80,60,70,60,75,85], then the stock spans would be [1,1,1,2,1,4,6].Implement the StockSpanner class:
StockSpanner() Initializes the object of the class.int next(int price) Returns the span of the stock's price given that today's price is price.
Example 1:
Input ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"] [[], [100], [80], [60], [70], [60], [75], [85]] Output [null, 1, 1, 1, 2, 1, 4, 6] Explanation StockSpanner stockSpanner = new StockSpanner(); stockSpanner.next(100); // return 1 stockSpanner.next(80); // return 1 stockSpanner.next(60); // return 1 stockSpanner.next(70); // return 2 stockSpanner.next(60); // return 1 stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price. stockSpanner.next(85); // return 6
Constraints:
1 <= price <= 10^510^4 calls will be made to next.
The description was taken from https://leetcode.com/problems/online-stock-span/.
#O(N) Time, O(N) Space Where N is Number of Function Calls
class StockSpanner:
def __init__(self):
self.stack = [] def next(self, price: int) -> int: span = 1
while self.stack and self.stack[-1][1] <= price:
span += self.stack.pop()[0]
self.stack.append([span, price])
return self.stack[-1][0]This problem revolves around knowing when the last greater price was.
For knowing when the next greater or lesser value is within a list or stream, a Monotonic Stack is fantastic.
What we can do to solve this problem is keep a span counter and a stack. While the price of the function call is greater than the top value on the stack, we will pop the previous span and price from the stack and increment the counter. Once we find a greater price in the stack, or we run out of days to traverse, we will push the new span count and current price onto the stack.
This will allow us to not only have to compare each price with each other price in the stream, but it will also allow us to reuse previously calculated spans.
Let's start by initializing an empty stack within the constructor.
class StockSpanner:
def __init__(self):
self.stack = []
Next, we will initialize a span count of one whenever the next function is called, since the current span is one day, today.
def next(self, price: int) -> int: span = 1
While the current price is greater than the price on the top of the stack, we will pop the stack and increment the span by the span saved within the stack, reusing previously calculated span values.
while self.stack and self.stack[-1][1] <= price:
span += self.stack.pop()[0]
Once we have done that, we will push the new span and current price onto the stack and return the top span value.
self.stack.append([span, price])
return self.stack[-1][0]