Monotonic Stack

Introduction

What is a monotonic stack? As the name suggests, a monotonic stack is a stack structure that satisfies monotonicity. Compared to a monotonic queue, it only allows insertion and deletion at one end.

For convenience, the following examples and pseudocode assume a monotonically increasing stack of integers.

Process

Insertion

When inserting an element into a monotonic stack, to maintain the stack's monotonicity, it is necessary to pop the minimum number of elements while ensuring that the entire stack satisfies monotonicity after inserting the element at the top.

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

When inserting element \(14\), to maintain monotonicity, elements \(0,11\) need to be popped in order. After the operation, the stack becomes \(\{14,45,81\}\).

The pseudocode is described as follows:

Implementation

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

Usage

Naturally, an element is read from the top of the stack, which satisfies one end of the monotonicity.

For example, the element retrieved in the example is the minimum value in the stack.

Applications

POJ3250 Bad Hair Day

There are \(N\) cows lined up from left to right, each with a height \(h_i\). Let the number of cows between the \(i\)-th cow from the left and "the first cow to its right with height \(≥h_i\)" be \(c_i\). Find \(\sum_{i=1}^{N} c_i\).

A basic application is this problem, which is a simple use of a monotonic stack. Record the position where each cow is popped. If it is never popped, set it to the farthest position. With slight processing, the required result can be calculated.

Additionally, monotonic stacks can also be used to solve RMQ problems offline.

We can sort all queries by their right endpoints, then scan the sequence from left to right to the right endpoint of the current query each time, inserting the scanned elements into the monotonic stack. This way, when answering each query, the values stored in the monotonic stack are decision points with positions \(\le r\) that could potentially be the answer, and these elements satisfy monotonicity. At this point, the first element in the monotonic stack with a position \(\ge l\) is the answer to the current query. This process can be implemented using binary search. The time complexity of using a monotonic stack to solve RMQ problems is \(O(q\log q + q\log n)\), and the space complexity is \(O(n)\).

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用