The Core Idea

A monotonic stack is just a stack that keeps its elements in sorted order (increasing or decreasing).
When a new element breaks the rule, we pop until the rule is happy again.

Why store indices instead of values?
Because we often need to know both:

The value → arr[stack.peek()]
Its position → stack.peek()

The Master Loop (Template Skeleton)

Here’s the heart of all our templates:

EditDeque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < arr.length; i++) {
    while (!stack.isEmpty() && /* comparison here */) {
        int idx = stack.pop();
        // Optionally assign answer for idx here
    }
    // Optionally assign answer for i here
    stack.push(i);
}

Every problem changes only two things:

The comparison (>, <, >=, <=)
Where you assign the answer (inside or outside the loop)

Templates 1–4: The Pure Forms

1. Next Greater Element (Strict)

Goal: First, greater element to the right correct, because we iterate left → right, and for each popped element we set the answer to the index of the next greater.
Stack type: Decreasing the stack holds indices of elements in decreasing order of their values, so when a bigger element comes in, it pops smaller ones.
Condition: arr[i] > arr[stack.peek()] correct strict comparison for “greater.”
Answer location: Inside the loop, you assign the answer for the popped element as soon as the next greater is found.

public static int[] nextGreater(int[] arr) {
    int[] ans = new int[arr.length];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
            int idx = stack.pop();
            ans[idx] = i; // store index of next greater
        }
        stack.push(i);
    }
    return ans;
}

2. Previous Greater Element (Strict)

Goal: First greater element to the left is correct, because we scan left → right, and for each element, whatever’s still in the stack after popping represents elements to the left.
Stack type: Decreasing indices in the stack correspond to values in decreasing order, so bigger values stay on top.
Condition: arr[i] >= arr[stack.peek()] This removes all elements smaller than or equal to the current one, so the next one on the stack is the first strictly greater to the left.
Answer location: After popping, you assign ans[i] only after removing smaller/equal values, because only then is the top of the stack (if any) the nearest greater-left element.

public static int[] prevGreater(int[] arr) {
    int[] ans = new int[arr.length];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[i] >= arr[stack.peek()]) {
            stack.pop();
        }
        if (!stack.isEmpty()) ans[i] = stack.peek();
        stack.push(i);
    }
    return ans;
}

3. Next Smaller Element (Strict)

Goal: First, smaller element to the right we scan left → right, and for each popped element, i is its next smaller index.
Stack type: Increasing the stack holds indices of elements in increasing order of values, so a smaller incoming value will pop bigger ones.
Condition: arr[i] < arr[stack.peek()] Correct strict comparison for “smaller.”

Answer location: Inside loop, as soon as a smaller element is found, you immediately assign the answer for the popped element.

  public static int[] nextSmaller(int[] arr) {
      int[] ans = new int[arr.length];
      Arrays.fill(ans, -1);
      Deque<Integer> stack = new ArrayDeque<>();

      for (int i = 0; i < arr.length; i++) {
          while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
              int idx = stack.pop();
              ans[idx] = i;
          }
          stack.push(i);
      }
      return ans;
  }

4. Previous Smaller Element (Strict)

Goal: First smaller element to the left is correct, because we scan left → right, and whatever remains on the stack after popping is from the left side.
Stack type: Increasing the stack holds indices in increasing value order, so when a smaller element is found to the left, it stays on top.
Condition: arr[i] <= arr[stack.peek()] Pops all elements larger than or equal elements so the top of the stack (if any) is strictly smaller than arr[i].
Answer location: After popping once, smaller elements are on top, and you take stack.peek() as the nearest smaller-to-left index.

public static int[] prevSmaller(int[] arr) {
    int[] ans = new int[arr.length];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) {
            stack.pop();
        }
        if (!stack.isEmpty()) ans[i] = stack.peek();
        stack.push(i);
    }
    return ans;
}

Templates 5–6: The Merged Versions

Sometimes, you want to access both the next and previous items in a single pass.
You can do it, but one of them will lose strictness (use >= or <= instead of > or <).

5. Next & Previous Greater in One Pass

Goal: First element to the right that is greater than or equal (next) and also first to the left that is greater (previous).
Stack: Decreasing bigger numbers stay, smaller/equal ones get popped.
Condition: arr[stack.peek()] <= arr[i]).
Answer location:
- Inside loop → next[idx] = i (right-side answer).
- After popping → prev[i] = stack.peek() (left-side answer).

public static int[][] nextAndPrevGreater(int[] arr) {
    int[] prev = new int[arr.length];
    int[] next = new int[arr.length];
    Arrays.fill(prev, -1);
    Arrays.fill(next, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
            int idx = stack.pop();
            next[idx] = i; // loses strictness here
        }
        if (!stack.isEmpty()) prev[i] = stack.peek();
        stack.push(i);
    }
    return new int[][] {prev, next};
}

6. Next & Previous Smaller in One Pass

Goal: First element to the right that is smaller than or equal (next) and also first to the left that is smaller (previous).
Stack: Increasing smaller values stay, bigger/equal ones are popped.
Condition: arr[stack.peek()] >= arr[i]. Equality means this is a non-strict version.
Answer location:
- Inside loop → next[idx] = i (right-side answer).
- After popping → prev[i] = stack.peek() (left-side answer).

public static int[][] nextAndPrevSmaller(int[] arr) {
    int[] prev = new int[arr.length];
    int[] next = new int[arr.length];
    Arrays.fill(prev, -1);
    Arrays.fill(next, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            int idx = stack.pop();
            next[idx] = i; // loses strictness here
        }
        if (!stack.isEmpty()) prev[i] = stack.peek();
        stack.push(i);
    }
    return new int[][] {prev, next};
}

Quick Reference Table

Template	Stack Type	While Condition	Answer Location	Strictness
1. Next Greater	Decreasing	`current > top`	Inside loop	Strict
2. Prev Greater	Decreasing	`current >= top`	Outside loop	Strict
3. Next Smaller	Increasing	`current < top`	Inside loop	Strict
4. Prev Smaller	Increasing	`current <= top`	Outside loop	Strict
5. Next+Prev Greater	Decreasing	`current >= top`	Both	One loses strictness
6. Next+Prev Smaller	Increasing	`current <= top`	Both	One loses strictness

Final Thoughts

The magic of monotonic stacks isn’t in memorizing a hundred variations, it’s realizing there’s only one loop, and the differences are just:

Increasing vs. decreasing stack.
Strict (>/<) vs. non-strict (>=/<=).
Assign the answer inside or outside the loop.

Monotonic Stack Template