Monotonic Stack

A monotonic stack is a stack data structure with elements in non-decreasing order from top to bottom. Elements can be efficiently pushed and popped while maintaining order.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class MonotonicStack {
  
  Stack<Integer> s = new Stack();

  void push(int n) {
    while (!s.isEmpty() && s.peek() > n) {
      s.pop();
    }
    s.push(n);
  }

  int min() {
    return s.peek();
  }

  void pop(int n) {
    if (!s.isEmpty() && n == s.peek()) {
      s.pop();
    }
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MonotonicStack {
  stack<int> s;
  
public:

  void push(int n) {
    while (!s.empty() && s.top() > n) {
      s.pop();
    }
    s.push(n);
  }

  int min() {
    return s.top();
  }

  void pop(int n) {
    if (!s.empty() && n == s.top()) {
      s.pop();
    }
  }
};

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class MonotonicStack:

  def __init__(self):
    self.s = []

  def push(self, n):
    while self.s and self.s[-1] > n:
      self.s.pop()
    self.s.append(n)

  def min(self):
    return self.s[-1]

  def pop(self, n):
    if self.s and n == self.s[-1]:
      self.s.pop()

Monotonic stacks provide efficient push/pop from top while maintaining ascending order. Useful for min tracking.

A monotonic stack is a specialized stack data structure that maintains its elements in a single, unbroken order—either entirely non-increasing or entirely non-decreasing. This kind of stack is useful in problems where you need to find the next greater or smaller element, maintaining an order property in a sequence, and various other application domains.

Solution

Below are examples of how a monotonic stack can be implemented in Java, C++, and Python. In these examples, we’ll maintain the elements in non-increasing order, i.e., the next element pushed onto the stack will be less than or equal to the element on the top.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Stack;

public class MonotonicStack {
    Stack<Integer> stack = new Stack<>();

    public void push(int value) {
        while (!stack.isEmpty() && stack.peek() < value) {
            stack.pop();
        }
        stack.push(value);
    }

    public int top() {
        return stack.peek();
    }

    public void pop() {
        stack.pop();
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stack>

class MonotonicStack {
    std::stack<int> stack;

public:
    void push(int value) {
        while (!stack.empty() && stack.top() < value) {
            stack.pop();
        }
        stack.push(value);
    }

    int top() {
        return stack.top();
    }

    void pop() {
        stack.pop();
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class MonotonicStack:
    def __init__(self):
        self.stack = []

    def push(self, value):
        while self.stack and self.stack[-1] < value:
            self.stack.pop()
        self.stack.append(value)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

These implementations use the typical stack operations with the modification in the push method to ensure that the monotonic property is maintained. The while loop inside the push method continues to pop elements from the top of the stack as long as they are less than the new element being inserted. This ensures that the elements in the stack always remain in non-increasing order.