The challenge
For every price, count consecutive days ending today with price ≤ today’s price.
Nonnegative prices; include today in its own span.
Example
[100,80,60,70,60,75,85] → [1,1,1,2,1,4,6].
Use the walkthrough below to inspect the input and each state change.
See Stock Span, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 14
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: [100,80,60,70,60,75,85]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Keep indices of strictly decreasing prices.
Indices are zero-based. C++ uses C++17 or later.
def solve(prices):
stack, answer = [], []
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
answer.append(i - (stack[-1] if stack else -1))
stack.append(i)
return answer
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
vector<int> solve(const vector<int>& prices) {
vector<int> stack, answer;
for (int i = 0; i < static_cast<int>(prices.size()); ++i) {
while (!stack.empty() && prices[stack.back()] <= prices[i]) stack.pop_back();
answer.push_back(i - (stack.empty() ? -1 : stack.back()));
stack.push_back(i);
}
return answer;
}