901. Online Stock Span

[fockspaces]

like daily temperature problem, I choose DP here. we can minimize the comparing times by recording the span for each day. so dp will looks like list of (price, span) pairs:

[(100, 1)] 
[(100, 1), (80, 1)] 
[(100, 1), (80, 1), (60, 1)] 
[(100, 1), (80, 1), (60, 1), (70, 2)] 

so if we add the next value 75, we find the price of prev 70 has 2 span, we can jump directly through 80. since 60 must be less than 75.

class StockSpanner:

    def __init__(self):
        self.dp = []

    def next(self, price: int) -> int:
        dp = self.dp
        if not dp:
            dp.append((price, 1))
        else:
            idx = len(dp) - 1
            while idx >= 0:
                cur_p, cur_span = dp[idx]
                if cur_p > price:
                    break
                idx -= cur_span
            dp.append((price, len(dp) - idx))
        return dp[-1][-1]

[fockspaces]

we can also implement with monotonic stack, since we only care "concecutive day", we can "squash" the previous elements into stack top (collapse).

[(100, 1)] 
[(100, 1), (80, 1)] 
[(100, 1), (80, 1), (60, 1)] 
[(100, 1), (80, 1), (60, 1), (70, 2)]  -> we can collapse this into [(100, 1), (80, 1), (70, 2)] 

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        stack = self.stack
        span = 1
        if not stack:
            stack.append((price, span))
            return span
        while stack and stack[-1][0] <= price:
            cur_p, cur_span = stack[-1]
            span += cur_span
            stack.pop()
        stack.append((price, span))
        return span

[fockspaces]

simplified version:

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        stack = self.stack
        span = 1
        while stack and stack[-1][0] <= price:
            span += stack[-1][-1]
            stack.pop()
        stack.append((price, span))
        return span