AIOJ

Introduction

What is a monotonic stack? As its name suggests, it is a stack whose elements satisfy a monotonicity condition. Unlike a monotonic queue, it supports insertion and removal at only one end.

For convenience, the examples and pseudocode below maintain a monotonically increasing stack of integers.

Process

Insertion

When inserting an element into a monotonic stack, pop as few elements as possible while ensuring that the whole stack remains monotonic after the new element is placed on top.

For example, suppose the elements in the stack from top to bottom are $\{0,11,45,81\}$ .

When inserting $14$ , maintaining monotonicity requires popping $0,11$ in succession; afterward, the stack becomes $\{14,45,81\}$ .

The pseudocode is as follows:

Implementation

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

Use

Simply read an element from the top of the stack; it satisfies one end of the monotonicity condition.

In the example above, the extracted element is the minimum in the stack.

Applications

POJ3250 Bad Hair Day

There are $N$ cows standing in a row from left to right. The height of each cow is $h_i$ . Let the $i$ -th cow from the left be followed by the first cow to its right whose height is $≥h_i$ , and let the number of cows between them be $c_i$ . Find $\sum_{i=1}^{N} c_i$ .

This is a basic application of a monotonic stack: record the position at which each cow is popped; if a cow is never popped, use the far endpoint. A little processing then yields the required result.

A monotonic stack can also be used to solve RMQ problems offline.

Sort all queries by their right endpoint. For each query, scan the sequence from left to right up to that endpoint and insert each scanned element into the monotonic stack. When answering a query, the stack contains the candidate decision points at positions $\le r$ that may become the answer, and these elements satisfy the monotonicity condition. The first element on the stack whose position is $\ge l$ is the answer to the current query; this step can be implemented with binary search. The time complexity of using a monotonic stack for RMQ is $O(q\log q + q\log n)$ , and the space complexity is $O(n)$ .

Monotonic Stack