Монотонный стек

Монотонный стек (Monotonic Stack)

Идея

Монотонный стек — это стек, в котором элементы поддерживают строгий порядок (возрастающий или убывающий). При добавлении нового элемента мы выталкиваем все элементы, нарушающие порядок.

Монотонно убывающий стек (сверху вниз — убывание):

Добавляем 4:          Добавляем 2:         Добавляем 5:
  |   |                 | 2 |                |   |
  | 4 |                 | 4 |                | 5 |
  | 7 |                 | 7 |                | 7 |
  +---+                 +---+                +---+
                                          (4 и 2 вытолкнуты)

Зачем нужен

Монотонный стек позволяет для каждого элемента найти ближайший больший/меньший элемент слева или справа за O(n).

Без монотонного стека: O(n²) — для каждого элемента ищем вправо/влево. С монотонным стеком: O(n) — каждый элемент добавляется и удаляется максимум один раз.

Задача 1: Next Greater Element

Условие: для каждого элемента найти первый больший элемент справа.

<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 * @return int[]
 */
function nextGreaterElement(array $nums): array
{
    $n = count($nums);
    $result = array_fill(0, $n, -1);
    $stack = []; // Stores indices

    for ($i = 0; $i < $n; $i++) {
        // While current element is greater than the element at stack top
        while (!empty($stack) && $nums[$i] > $nums[end($stack)]) {
            $idx = array_pop($stack);
            $result[$idx] = $nums[$i];
        }
        $stack[] = $i;
    }

    return $result;
}

// nums = [2, 1, 2, 4, 3]
//
// i=0, num=2: stack=[], push 0.        stack=[0]
// i=1, num=1: 1 < nums[0]=2, push 1.   stack=[0,1]
// i=2, num=2: 2 > nums[1]=1, pop 1 -> result[1]=2
//             2 = nums[0]=2 (not >), push 2. stack=[0,2]
// i=3, num=4: 4 > nums[2]=2, pop 2 -> result[2]=4
//             4 > nums[0]=2, pop 0 -> result[0]=4
//             push 3.                   stack=[3]
// i=4, num=3: 3 < nums[3]=4, push 4.   stack=[3,4]
//
// result = [4, 2, 4, -1, -1]

func nextGreaterElement(nums []int) []int {
	n := len(nums)
	result := make([]int, n)
	for i := range result {
		result[i] = -1
	}
	stack := []int{} // stores indices

	for i := 0; i < n; i++ {
		// While current element is greater than the element at stack top
		for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[idx] = nums[i]
		}
		stack = append(stack, i)
	}

	return result
}

// nums = [2, 1, 2, 4, 3]
// result = [4, 2, 4, -1, -1]

using System;
using System.Collections.Generic;

static int[] NextGreaterElement(int[] nums)
{
    int n = nums.Length;
    var result = new int[n];
    Array.Fill(result, -1);
    var stack = new Stack<int>(); // stores indices

    for (int i = 0; i < n; i++)
    {
        // While current element is greater than the element at stack top
        while (stack.Count > 0 && nums[i] > nums[stack.Peek()])
        {
            int idx = stack.Pop();
            result[idx] = nums[i];
        }
        stack.Push(i);
    }

    return result;
}

// nums = [2, 1, 2, 4, 3]
//
// i=0, num=2: stack=[], push 0.        stack=[0]
// i=1, num=1: 1 < nums[0]=2, push 1.   stack=[0,1]
// i=2, num=2: 2 > nums[1]=1, pop 1 -> result[1]=2
//             2 = nums[0]=2 (not >), push 2. stack=[0,2]
// i=3, num=4: 4 > nums[2]=2, pop 2 -> result[2]=4
//             4 > nums[0]=2, pop 0 -> result[0]=4
//             push 3.                   stack=[3]
// i=4, num=3: 3 < nums[3]=4, push 4.   stack=[3,4]
//
// result = [4, 2, 4, -1, -1]

def next_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []  # stores indices

    for i, num in enumerate(nums):
        # While current element is greater than the element at stack top
        while stack and num > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result

# nums = [2, 1, 2, 4, 3]
#
# i=0, num=2: stack=[], push 0.        stack=[0]
# i=1, num=1: 1 < nums[0]=2, push 1.   stack=[0,1]
# i=2, num=2: 2 > nums[1]=1, pop 1 -> result[1]=2
#             2 == nums[0]=2 (not >), push 2. stack=[0,2]
# i=3, num=4: 4 > nums[2]=2, pop 2 -> result[2]=4
#             4 > nums[0]=2, pop 0 -> result[0]=4
#             push 3.                   stack=[3]
# i=4, num=3: 3 < nums[3]=4, push 4.   stack=[3,4]
#
# result = [4, 2, 4, -1, -1]

## Задача 2: Daily Temperatures

Условие: для каждого дня найти, через сколько дней будет теплее.

<?php
declare(strict_types=1);

/**
 * @param int[] $temps
 * @return int[]
 */
function dailyTemperatures(array $temps): array
{
    $n = count($temps);
    $result = array_fill(0, $n, 0);
    $stack = []; // Day indices

    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $temps[$i] > $temps[end($stack)]) {
            $prevDay = array_pop($stack);
            $result[$prevDay] = $i - $prevDay;
        }
        $stack[] = $i;
    }

    return $result;
}

// temps = [73, 74, 75, 71, 69, 72, 76, 73]
// result = [1, 1, 4, 2, 1, 1, 0, 0]
//
// For 73 (day 0): next day 74 -> 1
// For 75 (day 2): after 4 days 76 -> 4
// For 76 (day 6): no warmer day -> 0

func dailyTemperatures(temps []int) []int {
	n := len(temps)
	result := make([]int, n)
	stack := []int{} // day indices

	for i := 0; i < n; i++ {
		for len(stack) > 0 && temps[i] > temps[stack[len(stack)-1]] {
			prevDay := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[prevDay] = i - prevDay
		}
		stack = append(stack, i)
	}

	return result
}

// temps = [73, 74, 75, 71, 69, 72, 76, 73]
// result = [1, 1, 4, 2, 1, 1, 0, 0]

using System.Collections.Generic;

static int[] DailyTemperatures(int[] temps)
{
    int n = temps.Length;
    var result = new int[n];
    var stack = new Stack<int>(); // day indices

    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && temps[i] > temps[stack.Peek()])
        {
            int prevDay = stack.Pop();
            result[prevDay] = i - prevDay;
        }
        stack.Push(i);
    }

    return result;
}

// temps = [73, 74, 75, 71, 69, 72, 76, 73]
// result = [1, 1, 4, 2, 1, 1, 0, 0]
//
// For 73 (day 0): next day 74 -> 1
// For 75 (day 2): after 4 days 76 -> 4
// For 76 (day 6): no warmer day -> 0

def daily_temperatures(temps: list[int]) -> list[int]:
    n = len(temps)
    result = [0] * n
    stack: list[int] = []  # day indices

    for i, temp in enumerate(temps):
        while stack and temp > temps[stack[-1]]:
            prev_day = stack.pop()
            result[prev_day] = i - prev_day
        stack.append(i)

    return result

# temps = [73, 74, 75, 71, 69, 72, 76, 73]
# result = [1, 1, 4, 2, 1, 1, 0, 0]
#
# For 73 (day 0): next day 74 -> 1
# For 75 (day 2): after 4 days 76 -> 4
# For 76 (day 6): no warmer day -> 0

Визуализация:

Температуры: [73, 74, 75, 71, 69, 72, 76, 73]
Индексы:       0   1   2   3   4   5   6   7

Стек (индексы):

i=0: 73. stack=[]         -> push. stack=[0]
i=1: 74 > 73.             -> pop 0, result[0]=1-0=1. push. stack=[1]
i=2: 75 > 74.             -> pop 1, result[1]=2-1=1. push. stack=[2]
i=3: 71 < 75.             -> push. stack=[2,3]
i=4: 69 < 71.             -> push. stack=[2,3,4]
i=5: 72 > 69, pop 4       -> result[4]=5-4=1
     72 > 71, pop 3       -> result[3]=5-3=2
     72 < 75.             -> push. stack=[2,5]
i=6: 76 > 72, pop 5       -> result[5]=6-5=1
     76 > 75, pop 2       -> result[2]=6-2=4
                          -> push. stack=[6]
i=7: 73 < 76.             -> push. stack=[6,7]

result = [1, 1, 4, 2, 1, 1, 0, 0]

Задача 3: Largest Rectangle in Histogram

Условие: массив высот столбцов гистограммы. Найти площадь наибольшего прямоугольника.

Высоты: [2, 1, 5, 6, 2, 3]

     +--+
     |  |
  +--+  |
  |  |  |
  |  |  |  +--+
+--+ |  +--+  |
|  | |  |  |  |
|  | |  |  |  |
+--+--+--+--+--+--+
  2  1  5  6  2  3

Наибольший прямоугольник: 5*2 = 10 (столбцы 5 и 6)

<?php
declare(strict_types=1);

/**
 * @param int[] $heights
 */
function largestRectangleHistogram(array $heights): int
{
    $stack = []; // Indices
    $maxArea = 0;
    $heights[] = 0; // Append 0 to flush remaining elements

    foreach ($heights as $i => $h) {
        while (!empty($stack) && $heights[end($stack)] > $h) {
            $height = $heights[array_pop($stack)];
            $width = empty($stack) ? $i : $i - end($stack) - 1;
            $maxArea = max($maxArea, $height * $width);
        }
        $stack[] = $i;
    }

    return $maxArea;
}

// heights = [2, 1, 5, 6, 2, 3]
// Answer: 10

func largestRectangleHistogram(heights []int) int {
	stack := []int{} // indices
	maxArea := 0
	heights = append(heights, 0) // sentinel to flush remaining

	for i, h := range heights {
		for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			height := heights[idx]
			width := i
			if len(stack) > 0 {
				width = i - stack[len(stack)-1] - 1
			}
			if area := height * width; area > maxArea {
				maxArea = area
			}
		}
		stack = append(stack, i)
	}

	return maxArea
}

// heights = [2, 1, 5, 6, 2, 3]
// Answer: 10

using System;
using System.Collections.Generic;

static int LargestRectangleHistogram(int[] heights)
{
    var stack = new Stack<int>(); // indices
    int maxArea = 0;
    // Collection expression with a spread + sentinel 0 to flush the stack
    List<int> bars = [.. heights, 0];

    for (int i = 0; i < bars.Count; i++)
    {
        while (stack.Count > 0 && bars[stack.Peek()] > bars[i])
        {
            int height = bars[stack.Pop()];
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, height * width);
        }
        stack.Push(i);
    }

    return maxArea;
}

// heights = [2, 1, 5, 6, 2, 3]
// Answer: 10

def largest_rectangle_histogram(heights: list[int]) -> int:
    stack: list[int] = []  # indices
    max_area = 0
    bars = [*heights, 0]  # sentinel 0 flushes the remaining elements

    for i, h in enumerate(bars):
        while stack and bars[stack[-1]] > h:
            height = bars[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# heights = [2, 1, 5, 6, 2, 3]
# Answer: 10

## Задача 4: Stock Span

Условие: для каждого дня найти количество подряд идущих дней до него (включая текущий), когда цена была <= текущей.

<?php
declare(strict_types=1);

/**
 * @param int[] $prices
 * @return int[]
 */
function stockSpan(array $prices): array
{
    $n = count($prices);
    $spans = array_fill(0, $n, 0);
    $stack = []; // Indices

    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $prices[end($stack)] <= $prices[$i]) {
            array_pop($stack);
        }

        $spans[$i] = empty($stack) ? $i + 1 : $i - end($stack);
        $stack[] = $i;
    }

    return $spans;
}

// prices = [100, 80, 60, 70, 60, 75, 85]
// spans  = [1,   1,  1,  2,  1,  4,  6]

func stockSpan(prices []int) []int {
	n := len(prices)
	spans := make([]int, n)
	stack := []int{} // indices

	for i := 0; i < n; i++ {
		for len(stack) > 0 && prices[stack[len(stack)-1]] <= prices[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) == 0 {
			spans[i] = i + 1
		} else {
			spans[i] = i - stack[len(stack)-1]
		}
		stack = append(stack, i)
	}

	return spans
}

// prices = [100, 80, 60, 70, 60, 75, 85]
// spans  = [1,   1,  1,  2,  1,  4,  6]

using System.Collections.Generic;

static int[] StockSpan(int[] prices)
{
    int n = prices.Length;
    var spans = new int[n];
    var stack = new Stack<int>(); // indices

    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && prices[stack.Peek()] <= prices[i])
        {
            stack.Pop();
        }

        spans[i] = stack.Count == 0 ? i + 1 : i - stack.Peek();
        stack.Push(i);
    }

    return spans;
}

// prices = [100, 80, 60, 70, 60, 75, 85]
// spans  = [1,   1,  1,  2,  1,  4,  6]

def stock_span(prices: list[int]) -> list[int]:
    n = len(prices)
    spans = [0] * n
    stack: list[int] = []  # indices

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] <= price:
            stack.pop()

        spans[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    return spans

# prices = [100, 80, 60, 70, 60, 75, 85]
# spans  = [1,   1,  1,  2,  1,  4,  6]

## Типы монотонных стеков

Тип	Порядок в стеке	Находит
Монотонно убывающий	Вершина < дно	Next Greater Element
Монотонно возрастающий	Вершина > дно	Next Smaller Element

Next Smaller Element

<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 * @return int[]
 */
function nextSmallerElement(array $nums): array
{
    $n = count($nums);
    $result = array_fill(0, $n, -1);
    $stack = [];

    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $nums[$i] < $nums[end($stack)]) {
            $idx = array_pop($stack);
            $result[$idx] = $nums[$i];
        }
        $stack[] = $i;
    }

    return $result;
}

// nums = [4, 8, 5, 2, 25]
// result = [2, 5, 2, -1, -1]

func nextSmallerElement(nums []int) []int {
	n := len(nums)
	result := make([]int, n)
	for i := range result {
		result[i] = -1
	}
	stack := []int{}

	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[i] < nums[stack[len(stack)-1]] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[idx] = nums[i]
		}
		stack = append(stack, i)
	}

	return result
}

// nums = [4, 8, 5, 2, 25]
// result = [2, 5, 2, -1, -1]

using System;
using System.Collections.Generic;

static int[] NextSmallerElement(int[] nums)
{
    int n = nums.Length;
    var result = new int[n];
    Array.Fill(result, -1);
    var stack = new Stack<int>();

    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && nums[i] < nums[stack.Peek()])
        {
            int idx = stack.Pop();
            result[idx] = nums[i];
        }
        stack.Push(i);
    }

    return result;
}

// nums = [4, 8, 5, 2, 25]
// result = [2, 5, 2, -1, -1]

def next_smaller_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and num < nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result

# nums = [4, 8, 5, 2, 25]
# result = [2, 5, 2, -1, -1]

### Previous Greater Element (обход справа налево)

<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 * @return int[]
 */
function previousGreaterElement(array $nums): array
{
    $n = count($nums);
    $result = array_fill(0, $n, -1);
    $stack = [];

    for ($i = $n - 1; $i >= 0; $i--) {
        while (!empty($stack) && $nums[end($stack)] <= $nums[$i]) {
            $idx = array_pop($stack);
            $result[$idx] = $nums[$i];
        }
        $stack[] = $i;
    }

    return $result;
}

func previousGreaterElement(nums []int) []int {
	n := len(nums)
	result := make([]int, n)
	for i := range result {
		result[i] = -1
	}
	stack := []int{}

	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && nums[stack[len(stack)-1]] <= nums[i] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[idx] = nums[i]
		}
		stack = append(stack, i)
	}

	return result
}

using System;
using System.Collections.Generic;

static int[] PreviousGreaterElement(int[] nums)
{
    int n = nums.Length;
    var result = new int[n];
    Array.Fill(result, -1);
    var stack = new Stack<int>();

    // Traverse right to left
    for (int i = n - 1; i >= 0; i--)
    {
        while (stack.Count > 0 && nums[stack.Peek()] <= nums[i])
        {
            int idx = stack.Pop();
            result[idx] = nums[i];
        }
        stack.Push(i);
    }

    return result;
}

def previous_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []

    # Traverse right to left
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] <= nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

## Шаблон

<?php
declare(strict_types=1);

/**
 * Generic monotonic stack template.
 *
 * @param int[] $nums
 * @return int[]
 */
function monotonicStackTemplate(
    array $nums,
    bool $findGreater = true,
    bool $findRight = true,
): array {
    $n = count($nums);
    $result = array_fill(0, $n, -1);
    $stack = [];

    $compare = $findGreater
        ? fn(int $a, int $b): bool => $a > $b
        : fn(int $a, int $b): bool => $a < $b;

    if ($findRight) {
        for ($i = 0; $i < $n; $i++) {
            while (!empty($stack) && $compare($nums[$i], $nums[end($stack)])) {
                $idx = array_pop($stack);
                $result[$idx] = $nums[$i]; // or $i for index
            }
            $stack[] = $i;
        }
    } else {
        for ($i = $n - 1; $i >= 0; $i--) {
            while (!empty($stack) && $compare($nums[$i], $nums[end($stack)])) {
                $idx = array_pop($stack);
                $result[$idx] = $nums[$i];
            }
            $stack[] = $i;
        }
    }

    return $result;
}

// monotonicStackTemplate is a generic monotonic stack template.
// findGreater: true = next greater, false = next smaller.
// findRight: true = search right, false = search left (previous).
func monotonicStackTemplate(nums []int, findGreater, findRight bool) []int {
	n := len(nums)
	result := make([]int, n)
	for i := range result {
		result[i] = -1
	}
	stack := []int{}

	compare := func(a, b int) bool { return a > b }
	if !findGreater {
		compare = func(a, b int) bool { return a < b }
	}

	process := func(i int) {
		for len(stack) > 0 && compare(nums[i], nums[stack[len(stack)-1]]) {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[idx] = nums[i]
		}
		stack = append(stack, i)
	}

	if findRight {
		for i := 0; i < n; i++ {
			process(i)
		}
	} else {
		for i := n - 1; i >= 0; i-- {
			process(i)
		}
	}

	return result
}

using System;
using System.Collections.Generic;

// MonotonicStackTemplate is a generic monotonic stack template.
// findGreater: true = next greater, false = next smaller.
// findRight: true = search right, false = search left (previous).
static int[] MonotonicStackTemplate(int[] nums, bool findGreater = true, bool findRight = true)
{
    int n = nums.Length;
    var result = new int[n];
    Array.Fill(result, -1);
    var stack = new Stack<int>();

    Func<int, int, bool> compare = findGreater
        ? (a, b) => a > b
        : (a, b) => a < b;

    void Process(int i)
    {
        while (stack.Count > 0 && compare(nums[i], nums[stack.Peek()]))
        {
            int idx = stack.Pop();
            result[idx] = nums[i]; // or i for index
        }
        stack.Push(i);
    }

    if (findRight)
    {
        for (int i = 0; i < n; i++)
        {
            Process(i);
        }
    }
    else
    {
        for (int i = n - 1; i >= 0; i--)
        {
            Process(i);
        }
    }

    return result;
}

from collections.abc import Callable

# Generic monotonic stack template.
# find_greater: True = next greater, False = next smaller.
# find_right: True = search right, False = search left (previous).
def monotonic_stack_template(
    nums: list[int],
    find_greater: bool = True,
    find_right: bool = True,
) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []

    compare: Callable[[int, int], bool] = (
        (lambda a, b: a > b) if find_greater else (lambda a, b: a < b)
    )

    def process(i: int) -> None:
        while stack and compare(nums[i], nums[stack[-1]]):
            idx = stack.pop()
            result[idx] = nums[i]  # or i for index
        stack.append(i)

    for i in range(n) if find_right else range(n - 1, -1, -1):
        process(i)

    return result

> **Запомни:** Монотонный стек решает задачи типа «для каждого элемента найти ближайший больший/меньший» за O(n). Каждый элемент входит в стек максимум один раз и выходит максимум один раз, поэтому суммарно O(n). Три ключевые задачи: Next Greater Element, Daily Temperatures, Largest Rectangle in Histogram.

Итоги

Монотонный стек поддерживает порядок элементов (возр. или убыв.)
Решает «next greater/smaller» за O(n) вместо O(n²)
Каждый элемент push/pop максимум один раз = O(n) итого
Largest Rectangle in Histogram — классика hard-задач
Храни индексы в стеке (не значения) — так удобнее считать расстояния