Next Greater Element

Given an array, for each element find the next greater element (NGE) — the first element to the right that is strictly larger. A monotonic (decreasing) stack keeps candidates and yields the answer for each index in one pass.

Idea

Scan from left to right. Maintain a stack of indices whose values are in decreasing order (top is smallest).
When you see a value a[i] greater than the value at the stack top, the NGE of that stack top is a[i]. Pop and assign, then repeat until stack is empty or top is ≥ a[i]. Then push i.
After the pass, any index left in the stack has no NGE (e.g. assign -1).

Template

Java
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // indices

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Next Smaller, Previous Greater/Smaller

Next smaller: Use a monotonic increasing stack (pop when current < stack top).
Previous greater: Scan right to left with a monotonic decreasing stack, or reverse the array and run “next greater” then reverse the result.
Previous smaller: Same idea with an increasing stack from the right.

Summary

Monotonic stack gives O(n) for “next/previous greater/smaller” for each index. Decreasing stack → next greater; increasing stack → next smaller. One pass, one stack.