A monotonic stack keeps elements in sorted order; when a new element breaks the order, everything it pops has just found its answer (its next greater or smaller element). Every element is pushed and popped at most once, so the total is O(n).
Template · O(n) time, O(n) space
defnext_greater(nums):
ans = [-1] *len(nums)
stack = [] # indices, values decreasing
for i, x inenumerate(nums):
while stack and nums[stack[-1]] < x:
ans[stack.pop()] = x # x is their next greater
stack.append(i)
return ans
vector<int> nextGreater(constvector<int>&nums) {
vector<int> ans(nums.size(), -1);
stack<int> st; // indices, values decreasing
for (int i =0; i < (int)nums.size(); i++) {
while (!st.empty() && nums[st.top()] < nums[i]) {
ans[st.top()] = nums[i]; // nums[i] is their next greater
st.pop();
}
st.push(i);
}
return ans;
}
Common pitfalls
Store indices, not values, when you need distances or widths
Decide strict vs non-strict comparison for equal elements
Remember to flush what is left on the stack at the end