Leetcode 901: Online Stock Span
Design a system that processes daily stock price quotes and computes the price span for the current day. The price span for a day is defined as the maximum number of consecutive days (including today) where the price of the stock was less than or equal to today’s price.
Problem
Approach
Steps
Complexity
Input: The input consists of a sequence of operations where a 'next' operation receives the stock price of the current day.
Example: Input: ["StockSpanner", "next", "next", "next", "next", "next", "next"]
[[], [120], [95], [100], [90], [130], [125]]
Constraints:
• 1 <= price <= 100000
• At most 10000 calls to the 'next' function.
Output: For each 'next' operation, output the price span for the provided stock price.
Example: Output: [null, 1, 1, 2, 1, 5, 2]
Constraints:
• Output is an integer for each 'next' operation, except the initialization which outputs null.
Goal: Compute the price span efficiently using a stack-based approach.
Steps:
• 1. Maintain a stack of price-span pairs.
• 2. For each new price, pop elements from the stack if they are less than or equal to the current price.
• 3. Sum the spans of the popped elements and include today's span (1).
• 4. Push the current price and its computed span onto the stack.
• 5. Return the span for the current day.
Goal: Constraints ensure efficient processing and valid input ranges.
Steps:
• Prices are guaranteed to be positive integers.
• The number of operations is capped at 10^4.
Assumptions:
• The input price is always a valid integer within the given range.
• The operations will always follow the sequence provided in the example.
• Input: Input: ["StockSpanner", "next", "next", "next", "next", "next", "next"]
[[], [90], [85], [95], [85], [110], [105]]
• Explanation: Output: [null, 1, 1, 3, 1, 5, 2]
Explanation: The span for each price is computed as follows:
1. [90]: Span = 1
2. [85]: Span = 1
3. [95]: Span = 3 (90, 85, 95)
4. [85]: Span = 1
5. [110]: Span = 5 (90, 85, 95, 85, 110)
6. [105]: Span = 2 (110, 105)
Approach: Use a stack-based approach to efficiently compute the span for each day's stock price.
Observations:
• Brute force computation for each day's span would result in O(n^2) time complexity.
• We can optimize using a stack to track previous prices and spans.
• A stack allows us to efficiently manage and compute spans by keeping track of relevant previous days.
Steps:
• 1. Initialize an empty stack to store pairs of (price, span).
• 2. For each price, pop all elements from the stack with a price less than or equal to the current price.
• 3. Add their spans to a running total.
• 4. Include today's span (1) and push the (price, span) pair onto the stack.
• 5. Return the computed span for the current price.
Empty Inputs:
• No empty inputs, as 'next' operations always receive a valid price.
Large Inputs:
• Handles maximum constraints with 10^4 operations and prices up to 10^5.
Special Values:
• Test cases with consecutive equal prices.
• Test cases with strictly increasing or decreasing prices.
Constraints:
• Input adheres to constraints and does not exceed operational limits.
public:
StockSpanner() {
}
int next(int price) {
int res = 1;
while(!cp.empty() && cp.top().first <= price) {
res += cp.top().second;
cp.pop();
}
cp.push(make_pair(price, res));
return res;
}
};
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner* obj = new StockSpanner();
* int param_1 = obj->next(price);
1 : Access Specifier
public:
Defines the access specifier for the following class methods and variables, making them accessible outside the class.
2 : Constructor
StockSpanner() {
Constructor for the StockSpanner class. Initializes the stack and prepares the object.
3 : Constructor Body
Placeholder for constructor body if needed in the future.
4 : Function Definition
int next(int price) {
Defines the next method, which calculates the span of stock prices for the current price.
5 : Variable Initialization
int res = 1;
Initializes the result variable to 1, which represents the span of the current stock price.
6 : Loop
while(!cp.empty() && cp.top().first <= price) {
Starts a loop that pops elements from the stack as long as the stack is not empty and the stock price is greater than the top element of the stack.
7 : Update Result
res += cp.top().second;
Updates the result by adding the span value of the top element of the stack.
8 : Pop Stack
cp.pop();
Pops the top element from the stack, as its span has been added to the result.
9 : Push Stack
cp.push(make_pair(price, res));
Pushes the current stock price and its corresponding span into the stack.
10 : Return Statement
return res;
Returns the calculated span for the current stock price.
Best Case: O(1) per operation when most prices are decreasing.
Average Case: O(1) amortized per operation due to stack operations.
Worst Case: O(n) for n operations, where all elements are popped once.
Description: Each element is pushed and popped from the stack at most once.
Best Case: O(1), when prices decrease consistently.
Worst Case: O(n), where n is the number of operations.
Description: Stack space depends on the number of elements stored.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus