LeetCode 901: Online Stock Span Solution
Master LeetCode problem 901 (Online Stock Span), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
901. Online Stock Span
Problem Explanation
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.
Solution Code
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;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 901 (Online Stock Span)?
This page provides optimized solutions for LeetCode problem 901 (Online Stock Span) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 901 (Online Stock Span)?
The time complexity for LeetCode 901 (Online Stock Span) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 901 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 901 in Java, C++, or Python.