Problem: MonotonicStack

Let’s look at a stack whose push has a different contract.

A monotonic stack keeps its values in decreasing order from bottom to top, ties allowed. The pop, top, and isEmpty operations behave exactly as they do on Stack, including the exceptions on an empty stack, and push still rejects null. The difference is in push. Before it adds the new value, it removes every element smaller than that value, from the top down, until the top is greater than or equal to that value.

The MinStack problem kept the whole Stack contract and added one operation. Here the four signatures are the same, but the contract of push is different. So we cannot extend the Stack interface to define the contract for MonotonicStack. We need a new one:

public interface MonotonicStack {
  void push(Integer item);  // evict, then add
  void pop();
  Integer top();
  boolean isEmpty();
}

public class ArrayMonotonicStack implements MonotonicStack { ... }

Here is a sequence of pushes and the monotonic stack after each one:

In the third row, pushing 8 evicted both 3 and 5, because both are smaller than 8.

Only strictly smaller elements are removed, so equal values can sit next to each other. Mathematicians call that order non-increasing.

The pop, top, and isEmpty operations must run in $O(1)$ worst-case time. A single push can evict everything, so its worst case is expensive. Part of this problem is to work out what push costs.