Sponsored
Sponsored
This approach utilizes a stack to track the prices and their corresponding spans. For each new price, we compare it with the top of the stack, which holds the last price and its span. If the new price is higher or equal, we pop from the stack and add the span of the popped element to the current span count. This way, we efficiently calculate the span while ensuring that older prices do not need to be recalculated unnecessarily.
Time Complexity: O(n), where n is the number of calls to next() because each element is pushed and popped from the stack at most once.
Space Complexity: O(n) for storing the stack.
1class StockSpanner {
2 constructor() {
3 this.stack = []; // Array of [price, span]
4 }
5
6 next(price) {
7 let span = 1;
8 while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
9 span += this.stack.pop()[1];
10 }
11 this.stack.push([price, span]);
12 return span;
13 }
14}The JavaScript solution adopts a similar approach using an Array for the stack. When a new price is encountered, it checks if this price is greater than the top of the stack's last price. If yes, it pops from the stack while accumulating the span of the popped elements. It then pushes the current price and accumulated span onto the stack.
This approach optimizes memory and simplifies the logic by storing prices along with pre-calculated spans in a tuple or similar structure. This implementation minimizes redundant span computation by leveraging tuple structures efficiently, ideal for platforms that can handle tuple operations swiftly.
Time Complexity: O(n), as each element is only processed once.
Space Complexity: O(n), where n is the number of calls, due to stack storage.
1import java.util.Stack;
2
3
The Java solution uses a stack of integer arrays to store prices and their computed spans. When searching for the span for a new price, it checks against the top element of the stack and if the top element's price is less than or equal to the new price, it pops the stack and increases the span accordingly. Finally, it pushes the new price and its span onto the stack.