Report Consecutive Historical Price Spans as Quotes Arrive
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Implement `StockSpanner()` and `next(price)`. Each next call appends today's price and returns the longest suffix of days, including today, whose prices are all at most today's price. The object retains earlier quotes across calls.
```cpp
class StockSpanner {
public:
StockSpanner();
int next(int price);
};
```
### Examples
**Example 1:**
```text
Input: construct StockSpanner(); call next(40), next(35), next(35), next(50)
Output: [1,1,2,4]
Explanation: The equal35s form a span of2;50 is at least all four recorded prices.
```
**Example 2:**
```text
Input: construct StockSpanner(); call next(10), next(8), next(9)
Output: [1,1,2]
Explanation: The final9 absorbs the preceding8, but the earlier10 stops its span.
```
### Constraints
- `1 <= price <= 10^5`.
- At most `10^4` next calls occur.
### Contract considerations
The original constructor and next method remain the public interface. Spans count consecutive days, not all historical qualifying prices.
```hint Read the boundary condition
An earlier block can be skipped as a whole if its largest boundary price does not exceed today's.
```
### Boundary reminders
The original constructor and next method remain the public interface. Spans count consecutive days, not all historical qualifying prices.
Overview: Report Consecutive Historical Price Spans as Quotes Arrive. Implement StockSpanner() and next(price).