= Solution
Use a <minimum stack>: each <linked list node> caches the <minimum> of all values from that node down to the bottom. This handles duplicate minima without searching when one is removed.
``
class Stack {
private class Node(val value: Int, val least: Int, val next: Node)
private var top: Node = null
def push(x: Int): Unit = {
val m = if (top == null) x else math.min(x, top.least)
top = new Node(x, m, top)
}
def pop(): Int = {
require(!isEmpty)
val x = top.value
top = top.next
x
}
def isEmpty: Boolean = top == null
def min: Int = {
require(!isEmpty)
top.least
}
}
``
The <representation invariant> is that the chain from `top` is finite and acyclic, and every reachable node `q` satisfies
$$
q.least=\begin{cases}q.value&q.next=null,\\\min(q.value,q.next.least)&q.next\ne null.\end{cases}
$$
The <abstraction function> takes the values along this chain in top-to-bottom order. Thus pushing $x$ changes $s$ to $x:s$, and popping a nonempty $s$ returns its head and leaves its tail. The cached-minimum equation follows for a new node from the previously valid chain; removing a head leaves every surviving equation unchanged. Consequently
$$
\boxed{push,pop,isEmpty,min\text{ each take }O(1)\text{ worst-case time}.}
$$
The bounds use the usual constant-cost allocation and <integer arithmetic> model. Storage is linear in the number of entries. `min` and `pop` require a nonempty <stack>; `min` leaves it unchanged.
Back to article page
