Span / dominance (Monotonic Stack Sub-pattern)
"How many consecutive earlier items are ≤ me?" is the distance to the previous greater. Pop everything ≤ the new value; the top is the wall that stops the span.
- ›
"span": consecutive previous days with price ≤ today
- ›
an online version (
next(price)called one by one) - ›
a pattern like i < j < k with a[i] < a[k] < a[j]
Stock Span uses indices: span = i − top (or i + 1 if the stack is empty). Online Stock Span has no array, so each stack entry stores (price, span) and a popped entry's span is added to the new one. 132 Pattern scans from the right and uses the pops differently: being popped proves a value has a bigger value to its left (a "3"), so it becomes a valid "2". Keep the largest such value, and any later (further left) value smaller than it completes the pattern.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Stock Span ProblemWalkthroughEasyBasic Anchor·GeeksforGeeks
- 2Online Stock SpanWalkthroughMediumBasic Reinforcement·LeetCode #901
- 3132 PatternWalkthroughMediumTricky / Edge Case·LeetCode #456
Template
// Stock span: how many consecutive days up to today had price <= today's.
// = distance to the previous strictly greater price. Decreasing stack of indices.
vector<int> stockSpan(vector<int>& price) {
int n = price.size();
vector<int> span(n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && price[st.top()] <= price[i]) // can never block anyone again
st.pop();
int prevGreater = st.empty() ? -1 : st.top(); // answer = top AFTER popping
span[i] = i - prevGreater;
st.push(i);
}
return span;
}