901. Online Stock Span
Explanation
We can solve this problem using a stack to keep track of the previous stock prices and their spans. Whenever a new price is encountered, we pop all the prices that are less than or equal to the current price to calculate the span. The span is the total number of consecutive days we are popping.
Algorithm
- Initialize an empty stack to store pairs of prices and spans.
- For each new price:
- Initialize the span as 1.
- While the stack is not empty and the top of the stack price is less than or equal to the current price:
- Pop the stack and add the popped span to the current span.
- Push the current price and span onto the stack.
- Return the span of the current price.
Time Complexity
- Each price is pushed and popped from the stack at most once, resulting in O(1) amortized time complexity for each next() call.
Space Complexity
- The space complexity is O(n), where n is the number of prices seen so far.
class StockSpanner {
Stack<int[]> stack;
public StockSpanner() {
stack = new Stack<>();
}
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;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.