37-Monotonic-Stack.md

Monotonic Stack

Problem Link

Practice Problem

---

Pattern

• Stack
• Monotonic Stack

---

Approach

Maintain a stack that is always increasing or decreasing depending on the next greater or smaller element requirement.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int[] nextSmallerElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= nums[i]) stack.pop();
            if (!stack.isEmpty()) ans[i] = stack.peek();
            stack.push(nums[i]);
        }
        return ans;
    }
}