Next / previous greater (Monotonic Stack Sub-pattern)
Decreasing stack. A bigger arrival pops every smaller waiting element and becomes their next greater. Whatever never gets popped has no answer.
- ›
"next greater element", "first bigger to the right"
- ›
"how many days until a warmer temperature"
- ›
circular array ("search wraps around")
- ›
cars catching up with each other and forming fleets
Next Greater Element I stores the answers in a map because they're asked for another array. Daily Temperatures pushes indices because the answer is a distance. Next Greater Element II loops twice over the circle (i % n). Car Fleet is the disguised one: sort cars by position from the target backwards and compute arrival times; a car that would arrive no later than the fleet ahead just joins it. The stack keeps fleet times that strictly increase.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Next Greater Element IWalkthroughEasyBasic Anchor·LeetCode #496
- 2Daily TemperaturesWalkthroughMediumBasic Reinforcement·LeetCode #739
- 3Next Greater Element II (circular)WalkthroughMediumSlight Variation·LeetCode #503
- 4Car FleetWalkthroughMediumPattern Transfer·LeetCode #853
Template
// Next greater element to the right; -1 if none. Decreasing stack of indices.
vector<int> nextGreater(vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1); // leftovers keep -1
stack<int> st; // indices; values decrease bottom → top
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) { // a[i] beats the waiting top
ans[st.top()] = a[i]; // answer written on POP
st.pop();
}
st.push(i); // a[i] now waits for its own answer
}
return ans;
}