✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-213

Monotonic Stacks

A Monotonic Stack is a stack that maintains its elements in increasing or decreasing order, making certain array and sequence problems solvable in linear time.

Explanation

Overview

A Monotonic Stack is a specialized stack in which elements are kept in a consistent order. When a new element violates the required order, elements are removed from the top until the ordering condition is restored.

How it works

Process the input elements from left to right or in another specified direction.; Compare the current element with the element at the top of the stack.; Remove elements while they violate the required monotonic order.; Use removed elements to answer the relevant problem query when appropriate.; Push the current element or its index onto the stack.

Key concepts

Monotonic order; Stack operations; Next greater element; Next smaller element; Unresolved elements; Amortized analysis

Types

name: Monotonic Increasing Stack; description: Maintains elements in non-decreasing or strictly increasing order, depending on the problem's requirements.; name: Monotonic Decreasing Stack; description: Maintains elements in non-increasing or strictly decreasing order, depending on the problem's requirements.

Time complexity

operation: Processing the entire array; complexity: O(n) amortized; operation: Stack Push; complexity: O(1); operation: Stack Pop; complexity: O(1)

Space complexity

O(n) in the worst case.

Example

array: 2; 1; problem: Find the next greater element for each array position.; results: element: 2; nextGreater: 4; element: 1; nextGreater: 4; explanation: A decreasing stack stores unresolved elements. When a greater value appears, it resolves the next-greater-element queries for smaller elements at the top.

Example or application

Array

  • 2

  • 1

  • 4

  • 3

  • 5

Problem

Find the next greater element for each array position.

Results

ElementNext Greater

2

4

1

4

4

5

3

5

5

Explanation

A decreasing stack stores unresolved elements. When a greater value appears, it resolves the next-greater-element queries for smaller elements at the top.

Definition

A Monotonic Stack is a specialized stack in which elements are kept in a consistent order. When a new element violates the required order, elements are removed from the top until the ordering condition is restored.

Types

NameDescription

Monotonic Increasing Stack

Maintains elements in non-decreasing or strictly increasing order, depending on the problem's requirements.

Monotonic Decreasing Stack

Maintains elements in non-increasing or strictly decreasing order, depending on the problem's requirements.

How It Works

  • Process the input elements from left to right or in another specified direction.

  • Compare the current element with the element at the top of the stack.

  • Remove elements while they violate the required monotonic order.

  • Use removed elements to answer the relevant problem query when appropriate.

  • Push the current element or its index onto the stack.

Implementation

Language

Pseudocode

Code

  • function nextGreaterElements(array):

  • stack = empty stack

  • result = array filled with -1

  • for i from 0 to length(array) - 1:

  • while stack is not empty and array[i] > array[stack.top()]:

  • index = stack.pop()

  • result[index] = array[i]

  • stack.push(i)

  • return result

Time Complexity

OperationComplexity

Processing the entire array

O(n) amortized

Stack Push

O(1)

Stack Pop

O(1)

Space Complexity

O(n) in the worst case.

Key Concepts

  • Monotonic order

  • Stack operations

  • Next greater element

  • Next smaller element

  • Unresolved elements

  • Amortized analysis

Advantages

  • Can reduce many nested-loop problems from O(n²) to O(n).

  • Each element is pushed and popped at most once in common applications.

  • Provides an efficient way to find nearby greater or smaller elements.

  • Uses a simple stack-based implementation.

Limitations

  • The correct increasing or decreasing order depends on the problem.

  • Handling duplicate values requires careful comparison conditions.

  • The method is most useful when queries have a suitable nearest-element structure.

Applications

  • Next greater element

  • Next smaller element

  • Previous greater or smaller element

  • Largest rectangle in a histogram

  • Stock span problems

  • Trapping rainwater

Related Topics

  • Stacks

  • Monotonic Queues

  • Array Algorithms

  • Amortized Complexity

Practice Questions

QuestionAnswer

What is a Monotonic Stack?

A stack that maintains its elements in increasing or decreasing order.

What is a common application of a Monotonic Stack?

Finding the next greater or next smaller element.

Why can the algorithm run in O(n) time?

Each element is pushed once and popped at most once.

Learning Objectives

  • Explain the central idea and purpose of monotonic stacks.

  • Identify the assumptions, inputs, and conditions relevant to monotonic stacks.

  • Evaluate an application of monotonic stacks for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures