Problem Statement
leetcode problem link
Brute Force [TLE]
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
self.stack.append(price)
st = []
count = 0
while self.stack:
val = self.stack.pop()
st.append(val)
if val > price:
break
count += 1
while st:
self.stack.append(st.pop())
return count
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
Stack approach [Accepted]
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
spanning_day = 0
while self.stack and self.stack[-1][0] <= price:
_, day = self.stack.pop()
spanning_day += day
self.stack.append([price, spanning_day + 1])
return spanning_day + 1
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
Editorial
Approach: Monotonic Stack
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
ans = 1
while self.stack and self.stack[-1][0] <= price:
ans += self.stack.pop()[1]
self.stack.append([price, ans])
return ans
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
