Maintain a decreasing stack of indices to find each element's next greater neighbor in one pass.
Maintain a stack of indices whose values are in decreasing order. Scan left-to-right: when the current value is larger than the value at the top index, pop and resolve that index, because the current element is its next-greater. Push the current index and keep going. Indices still on the stack when the scan ends have no next-greater element.
Keep a stack of "unresolved" indices (in decreasing value order). When arr[i] > arr[top], pop and record arr[i] as the next-greater for the popped index. After the pop-loop, push i. One pass resolves every index that has a larger successor.
Push: when arr[i] ≤ arr[top], the current value is not yet the answer for anything, so push i onto the stack and move on. Pop-and-Resolve: when arr[i] > arr[top], the current value IS the next-greater for the top index, so pop it, record the answer and repeat the check.
Each index is pushed once and popped at most once, so the total work across all iterations is O(n). The stack holds at most n indices at a time, so O(n) auxiliary space.
Monotonic stack is used in problems like "daily temperatures", "next greater element II" (circular), "largest rectangle in histogram", and stock span. The same pattern works for next-smaller by flipping the comparison.