Monotonic Decreasing Stack

Non-increasing order means that as you move through a sequence or set, the values always get smaller or stay the same - they never get larger.

For example:

[5, 5, 3, 2, 2, 1] is in non-increasing order. As you move through the sequence, the numbers never increase.

[10, 6, 4, 4, 2] is also non-increasing. Each number is less than or equal to the number before it.

But [2, 4, 1, 3] is NOT non-increasing, because 1 and 3 are larger than numbers before them.

Another way to think of it is:

Non-decreasing means the values can increase or stay the same
Non-increasing means the values can decrease or stay the same

So in non-increasing order, elements always get smaller or equal - never larger. This descending ordering is useful for algorithms like sorting stacks and queues where newest/max elements get added on top or back.

The key is that non-increasing sequence has no increasing steps. Values always descend or stay steady.

A monotonic decreasing stack is a stack data structure where the elements are in non-increasing 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 max() {
    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
class MonotonicStack {
  stack<int> s;
  
public:
  void push(int n) {
    while (!s.empty() && s.top() < n) {
      s.pop();
    }
    s.push(n);
  }

  int max() {
    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 max(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 descending order. Useful for max tracking.

A monotonic stack is a general concept where the elements in the stack are arranged in a single, unbroken order. This order can either be non-increasing or non-decreasing.

A Monotonic Decreasing Stack is a specific type of monotonic stack where the elements are arranged in a non-increasing order. This means that each element in the stack is less than or equal to the element below it. It ensures that the stack’s top element is always the smallest among the current elements, and the order is maintained as elements are pushed and popped from the stack.

In summary, a Monotonic Decreasing Stack is a particular case of a monotonic stack that specifically maintains its elements in a non-increasing order. It is useful in problems that require keeping track of minimum values or where the ordering of elements in a specific way is essential.

A monotonic decreasing stack is a data structure that maintains its elements in a decreasing order. The idea is to always ensure that the elements inside the stack are arranged in a way that the topmost element is the smallest. When a new element that is smaller than the topmost element is encountered, it is simply pushed onto the stack. If it is larger, elements are popped from the stack until a smaller element is encountered, or the stack is empty, and then the new element is pushed. This kind of structure is beneficial in scenarios like finding the nearest smaller elements, or in problems related to histograms, etc.

Solution

Java

Here’s a Java implementation of a monotonic decreasing stack:

 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 MonotonicDecreasingStack {
    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++

A C++ implementation of a monotonic decreasing stack:

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

class MonotonicDecreasingStack {
    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

Here’s how you can implement a monotonic decreasing stack in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class MonotonicDecreasingStack:
    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()

In these implementations, the push method ensures that the elements in the stack are in a decreasing order by removing elements from the top that are less than the new element. The top method returns the current top element, and the pop method can be used to remove an element from the top of the stack.