Back to DSA
Online Stock Span
mediumCreate a class that processes a sequence of daily stock prices one at a time and for each new price reports its span. The span for a given day is the largest number of consecutive days ending on (and including) that day during which the price never exceeded the current day's price.
Examples
Example 1:
Input:
StockSpanner(), next(50), next(40), next(30), next(35), next(25), next(45), next(55)Output:
[null,1,1,1,2,1,5,7]Hints
import java.util.*;
class StockSpanner {
private Deque<int[]> stack = new ArrayDeque<>();
public int next(int price) {
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
span += stack.pop()[1];
}
stack.push(new int[]{price, span});
return span;
}
}Time complexity
O(1) amortizedSpace complexity
O(n)