A monotonic stack keeps elements in increasing or decreasing order. It’s used for “next greater/smaller element”, stock span, and histogram problems, often in O(n) time by pushing/popping each element at most once.
function nextGreater(nums: number[]): number[] {
const res = Array(nums.length).fill(-1);
const st: number[] = []; // stack of indices
for (let i = 0; i < nums.length; i++) {
while (st.length && nums[st[st.length - 1]] < nums[i]) {
res[st.pop()!] = nums[i];
}
st.push(i);
}
return res;
}