Стек рекордов (стек минимумов / максимумов)

TL;DR: Стек минимумов (максимумов) — это элементы массива, правее которых до текущего индекса $i$ нет меньших (бóльших) элементов. Часто используется вместо деревьев отрезков и других более сложных структур данных в задачах, где необходимо понимать структуру массива относительно запросов поиска минимума или максимума на отрезке. Строится последовательно для индексов по возрастанию: чтобы из стека минимумов (максимумов) для индекса $i-1$ получить стек минимумов (максимумов) для индекса $i$, нужно удалить из стека все индексы, значения которых не меньше (не больше) $a_i$, а затем добавить индекс $i$ в конец стека. Такое построение суммарно занимает $O(n)$ времени. Для большего понимания обратитесь к картинке и коду ниже. На английском языке стек рекордов известен под названием «monotonic stack».

Стек рекордов или стек минимумов или максимумов (не путать со стеком с минимумом) — очень простая, но при этом очень мощная структура данных, которая во многих задачах может заменить такие более сложные структуры данных как дерево отрезков. При этом в силу ее простоты, отдельное время во время изучения алгоритмов ей не уделяется, поэтому в интернете сложно найти какие-либо материалы по этой теме.

Пример задачи

Рассмотрим стандартный пример задачи, в которой можно применить стек рекордов.

Задача: Дан массив целых чисел $a$ длины $n$. Необходимо найти сумму минимумов по всем его подотрезкам или другими словами $\sum_{l =0}^{n-1} \sum_{r = l}^{n-1} \min(a_l, a_{l + 1}, \ldots, a_r)$.

Очевидным решением за $O(n^3)$ будет перебрать все отрезки и для каждого из них найти минимум. Если зафиксировать левую границу отрезка и перебирать правую по возрастанию, можно поддерживать минимум на лету. Такое решение будет работать за $O(n^2)$. Однако, чтобы продолжить улучшать асимптотику, необходимо сменить перспективу.

Заметим, что минимум на любом отрезке равен какому-то конкретному элементу на этом отрезке (а именно, минимуму). Для простоты пока предположим, что все элементы массива различны. Тогда зафиксируем для каждого отрезка такой элемент. Нам необходимо найти сумму всех таких чисел. Давайте поменяем точку зрения: вместо того чтобы для каждого отрезка рассматривать минимум, мы для каждого элемента $a_i$ массива посчитаем значение $cnt_i$: для скольки отрезков он является минимумом. Тогда ответом на задачу будет $\sum_{i=0}^{n-1} a_i \cdot cnt_i$. Нам остается лишь найти эти значения $cnt_i$. Но в каком случае $a_i$ является минимумом на каком-то отрезке $[l, r]$? Во-первых, элемент $a_i$ должен лежать на этом отрезке, а во-вторых, все остальные элементы на отрезке должны быть больше $a_i$. В частности, все элементы на отрезке $[l, i - 1]$ больше $a_i$ и все элементы на отрезке $[i + 1, r]$ больше $a_i$. И если это так, то любой такой отрезок $[l, r]$ нам подходит. Тогда предположим, что $l_0$ — это ближайший индекс слева от $i$, такой что $a_{l_0} < a_i$, и $r_0$ — ближайший справа от $i$ такой индекс. Тогда очевидно, что $l$ должно быть больше $l_0$, потому что иначе отрезок $[l, i + 1]$ будет содержать $l_0$, а также $r$ должно быть меньше $r_0$, потому что иначе отрезок $[i + 1, r]$ будет содержать $r_0$. При этом если $l_0 < l \le i \le r < r_0$, то любой такой отрезок нам подходит, ведь он содержит индекс $i$ и при этом не содержит никаких элементов, меньших $a_i$. Существует $i - l_0$ подходящих левых границ и $r_0 - i$ подходящих правых границ, и нам подходит любая такая пара, так что $cnt_i = (i - l_0) \cdot (r_0 - i)$. Остается лишь для каждого индекса $i$ найти ближайшие слева и справа элементы, которые меньше $a_i$. В этот момент вам, возможно, хочется сказать «наверное, это как-то делается через дерево отрезков», но не стоит попадать в эту ловушку! Стек минимумов — это как раз таки ровно структура данных, которая позволяет для каждого элемента массива найти ближайший меньший элемент всего в несколько строчек кода без использования каких-либо сложных структур данных типа дерева отрезков.

Но перед тем как мы перейдем непосредственно к рассмотрению стека минимумов, сначала мы должны исправить пару неаккуратностей, которые мы допустили в алгоритме выше. Во-первых, что делать, если таких индексов $l_0$ или $r_0$ не существует? Что, если нет ни одного элемента левее $a_i$, который был бы его меньше? В таком случае в качестве левой границы мы можем выбрать любой индекс от $0$ до $i$. Иными словами, можно считать, что $l_0 = -1$. Аналогично для правой границы можно считать, что $r_0 = n$. Это можно понимать немного иначе, представив, что в массиве есть дополнительные элементы $a_{-1}$ и $a_n$, которые равны $-\infty$, и поэтому у каждого элемента массива всегда есть элементы слева и справа, которые меньше. Вторая проблема — это то, что мы считали, что все элементы массива различны. Если в массиве есть одинаковые элементы, то на отрезках может быть несколько элементов, равных минимуму, и нам нужно точно определить, какой из них мы выберем, чтобы случайно не посчитать один и тот же отрезок несколько раз. Не умаляя общности, можно считать, что мы всегда выбираем самый правый среди минимумов на отрезке (можно было выбрать самый левый; главное — зафиксировать выбор и следовать ему). Это значит, что все элементы на отрезке правее него строго меньше его, а все элементы на отрезке левее него меньше или равны ему. То есть на самом деле нам надо найти не ближайшие слева и справа элементы, меньшие данного, а слева найти ближайший меньший, а справа ближайший не больший. Кардинально это никак алгоритм не поменяет. Альтернативный способ избавиться от проблемы равных чисел — это представить, что массив состоит не из элементов $a_i$, а из пар $(a_i, i)$, которые сравниваются лексикографически (сначала по первому элементу, а при равенстве первого элемента, по второму). В таком случае все элементы массива точно будут различны, так что минимум на любом отрезке будет единственен. На самом деле это в точности соответствует нашему предыдущему способу, если бы среди равных чисел мы выбирали самое левое, потому что если на отрезке есть несколько элементов с одинаковым значением, то меньшим среди них будет элемент с минимальным индексом.

Определение, свойства и построение стека минимумов

Теперь перейдем непосредственно к стеку минимумов, и как он может помочь нам найти для каждого индекса массива ближайший слева меньший элемент. Для начала определим, что такое стек минимумов.

Определение: Стек минимумов (стек рекордов) для индекса $i$ массива $a$ — это возрастающая последовательность индексов массива $a$, такая что индекс $j \le i$ находится в этой последовательности тогда и только тогда, когда $a_j$ строго меньше всех остальных элементов на отрезке $[j, i]$. Если же вместо строго меньше в предыдущем предложении написать строго больше, то такая последовательность называется стеком максимумов.

В частности, последним элементом стека минимумов для индекса $i$ всегда является индекс $i$, потому что $a_i$ больше всех остальных элементов на отрезке $[i, i]$, потому что это единственный элемент на этом отрезке. Первым же элементом в стеке минимумов индекса $i$ является индекс минимума на отрезке $[0, i]$ (самый правый, если есть несколько элементов, равных минимуму), потому что он удовлетворяет условию на вхождение в стек минимумов, но никакой элемент левее него не может удовлетворять этому условию, иначе он был бы меньше минимума. В зависимости от контекста для удобства иногда считают, что первым элементом стека минимумов является $-1$ (подразумевая, что в начале массива есть элемент $a_{-1} = -\infty$).

Почему же эта структура называется стеком рекордов? Если мы встанем в точку $i$ и пойдем налево, то элементы стека минимумов будут в точности «рекордными» значениями, которые меньше всего, что мы видели до этого. В частности, из этого легко сделать вывод, что не только индексы в стеке минимумов строго возрастают, но и соответствующие им значения в массиве $a$. Также это значит, что если $j$ и $k$ — последовательные элементы стека рекордов индекса $i$, то элемент $a_k$ является минимумом (самым правым минимумом, если в массиве могут быть одинаковые элементы) на отрезках с правой границей $i$ тогда и только тогда, когда левая граница такого отрезка $l$ строго больше $j$ и не больше $k$ ($j < l \le k$). Эта идея является ключевой в одном из главных алгоритмов, использующем стек рекордов, — вариации алгоритма Тарьяна для поиска минимума на отрезке в оффлайне. Тем самым весь массив до индекса $i$ имеет очень конкретную структуру относительно элементов стека минимумов: элементы стека минимумов — это строго возрастающая последовательность элементов, а все элементы между двумя последовательными элементами стека минимумов не меньше их обоих. Если нарисовать элементы массива как точки $(i, a_i)$ на плоскости, то мы также сможем получить и красивую визуальную геометрическую интуицию:

test

Здесь красные точки — это элементы стека минимумов, а черные — все остальные. Обратите внимание, что все остальные элементы между двумя элементами стека минимумов не меньше их обоих, поэтому все элементы лежат внутри синих стаканов.

Кроме того, если мы обозначим стек минимумов для индекса $i$ как последовательность $j_0$, $j_1$, $\ldots$, $j_m$, то, как мы уже поняли, $j_0 = -1$ и $j_m = i$, но кроме того, для любого индекса $j_k$ в стеке минимумов, $j_{k-1}$ является для него тем самым ближайшим слева меньшим элементом (это становится очевидно, если вспомнить процесс, когда мы встаем в индекс $i$ и идем налево в поиске «рекордов»). И эта идея как раз таки позволяет нам найти то, что мы хотели, — ближайший слева от $i$ индекс $l$, такой что $a_l < a_i$, ведь если у нас уже есть стек минимумов, то этот индекс $l$ — это просто предпоследний элемент стека минимумов $j_{m-1}$.

Мы обсудили основные свойства стека минимумов, и, надеюсь, теперь вы согласны, что он имеет фундаментальное значение для понимания структуры массива. В частности, он поможет нам решить задачу поиска суммы минимумов по всем подотрезкам массива. Последний шаг, который нам остается, — это, собственно, найти стеки минимумов для всех индексов массива. Обратите внимание, что сохранить их все у нас вряд ли получится, потому что, к примеру, если массив $a$ возрастающий, то стек минимумов для индекса $i$ содержит все индексы от $-1$ до $i$, поэтому суммарный размер всех стеков минимумов будет квадратичным относительно размера массива. Мы же сделаем нечто немного другое: мы будем перебирать индексы массива $a$ по возрастанию и преобразовывать стек минимумов для индекса $i-1$ в стек минимумов для индекса $i$ шаг за шагом. Таким образом, в момент, когда мы находимся в индексе $i$, перед нами стек минимумов для индекса $i$, который мы можем использовать.

Как же поменяется стек минимумов, если мы перейдем от индекса $i-1$ к индексу $i$? Вспомним определение: стек минимумов — это последовательность всех индексов $j$, таких что $a_j$ меньше всех других элементов на отрезке от $j$ до $i-1$. Если какой-то элемент $a_j$ не был меньше всех элементов правее него, то при добавлении элемента $a_{i}$ он таковым не станет. А если элемент $j$ был в стеке минимумов, то он уже точно меньше всех элементов от $j$ до $i-1$, так что он должен остаться в стеке минимумов тогда и только тогда, когда он меньше $a_{i}$. Так как мы уже знаем, что значения в массиве $a$ элементов стека минимумов возрастают, то все индексы $j$, которые не удовлетворяют этому условию, находятся на конце стека. То есть алгоритм пересчета стека минимумов следующий: мы удаляем индексы $j$ с вершины стека, пока $a_j \ge a_{i}$, после чего, когда такие элементы закончились, добавляем индекс $i$ на вершину стека. И это все! На самом деле все очень просто. Надеюсь, теперь стало понятно, почему такую последовательность мы назвали стеком. Для большего понимания алгоритма рекомендую посмотреть на код:

// a -- array of length n
vector<int> stack_of_min;
for (int i = 0; i < n; i++) {
    while (!stack_of_min.empty() && a[stack_of_min.back()] >= a[i]) {
        stack_of_min.pop_back();
    }
    stack_of_min.push_back(i);
    // use stack_of_min as a stack of minimums for index i
}

Такой алгоритм работает за линейное время, потому что каждый индекс массива добавляется в стек один раз, а значит, удалить из стека рекордов мы можем не более $n$ элементов за все время.

Вы можете обратить внимание, что в коде сверху мы используем std::vector вместо стека. Это связано с тем, что в более продвинутых контекстах нам может хотеться использовать не только последний элемент этого стека, но и иметь доступ к другим элементам. В зависимости от ситуации, как мы уже обсуждали, бывает полезно добавить изначально в стек элемент $-1$, и тогда проверка !stack_of_min.empty() превращается в stack_of_min.back() != -1. В частности, это может помочь избежать разбора случаев в задаче поиска суммы минимумов по всем подотрезкам массива, которую мы, собственно, уже почти решили. Мы научились искать для каждого элемента массива ближайший меньшей слева (это вершина стека перед добавлением индекса $i$ в конец). Теперь, чтобы найти ближайший справа меньший или равный, нужно запустить аналогичный цикл, но по убыванию индексов (положив изначально $n$ в стек), и удалять элементы, пока они строго больше $a_i$ (легко запомнить, что мы удаляем элементы, пока они не удовлетворяют необходимому нам условию: если нам нужен ближайший меньший, мы удаляем, пока он не меньше, если нам нужен ближайший меньший или равный, мы удаляем, пока он больше, если нам нужен ближайшие больший, мы удаляем, пока он не больше, если нам нужен ближайший больший или равный, мы удаляем, пока он меньше). Когда мы нашли те самые нужные индексы слева и справа, ответ на задачу выражается через них простой формулой, как мы уже говорили ранее. С полным решением задачи можно ознакомиться по ссылке.

Замечание: Если мы кроме прохода со стеком минимумов еще сохраним для каждого индекса $i$ значение $pr_i$ (индекс ближайшего слева меньшего элемента), то чтобы позже восстановить стек минимумов индекса $i$, нужно рассмотреть индексы $i$, $pr_i$, $pr_{pr_i}$, $pr_{pr_{pr_i}}$, $\ldots$. Тем самым, в случае, когда нам нужно иметь доступ к стеку минимумов в онлайне, мы можем воспользоваться идеей из персистентного Convex Hull Trick. Но в реальности в подавляющем числе случаев оффлайн прохода со стеком достаточно.

Стек минимумов без стека минимумов

Если нам нужно просто найти ближайший слева меньший элемент, то на самом деле явным образом хранить стек минимумов необязательно, ведь, как мы знаем, он как раз таки состоит из элементов $i$, $pr_i$, $pr_{pr_i}$, $pr_{pr_{pr_i}}$ и так далее. В таком случае удаление элемента с вершины стека равноценно переходу по ссылке $pr$ к следующему элементу. Такое решение выражается в следующий код:

// a -- array of length n
for (int i = 0; i < n; i++) {
    pr[i] = i - 1;
    while (pr[i] >= 0 && a[pr[i]] >= a[i]) {
        pr[i] = pr[pr[i]];
    }
}

Этот код на самом деле делает все те же самые операции, что и решение со стеком, поэтому тоже работает за линейное время. Однако нам не надо поддерживать стек, и код стал чище. По духу это решение похоже на алгоритм поиска префикс-функции.

Один проход со стеком вместо двух

Для простоты предположим, что все элементы массива различны. Тогда пока мы ищем ближайший слева элемент, меньший текущего, и удаляем элементы со стека, мы можем одновременно искать ближайший больший удаляемых элементов. Им будет наш текущий элемент, ведь мы как раз удаляем элемент с вершины стека ровно в тот момент, когда мы нашли меньший элемент.

// a -- array of length n
vector<int> stack_of_min;
vector<int> pr_l(n, -1); // closest smaller to the left
vector<int> pr_r(n, n); // closest smaller or equal to the right
for (int i = 0; i < n; i++) {
    while (!stack_of_min.empty() && a[stack_of_min.back()] >= a[i]) {
        pr_r[stack_of_min.back()] = i;
        stack_of_min.pop_back();
    }
    if (!stack_of_min.empty()) {
        pr_l[i] = stack_of_min.back();
    }
    stack_of_min.push_back(i);
}

В случае, если элементы в массиве могут совпадать, данный код найдет ближайший слева меньший и ближайший справа меньший или равный элементы массива. Для того чтобы и справа найти ближайший меньший, придется хранить дополнительную информацию в стеке. Но на самом деле, как и в примере с поиском суммы минимумов по всем подотрезкам, в большинстве задач мы как раз таки и хотим найти ближайший слева меньший, а справа меньший или равный.

Описанные выше два подхода можно объединить в один код, который без стека находит ближайший слева меньший и ближайший справа меньший или равный:

// a -- array of length n
vector<int> pr_l(n, -1); // closest smaller to the left
vector<int> pr_r(n, n); // closest smaller or equal to the right
for (int i = 0; i < n; i++) {
    pr_l[i] = i - 1;
    while (pr_l[i] >= 0 && a[pr_l[i]] >= a[i]) {
        pr_r[pr_l[i]] = i;
        pr_l[i] = pr_l[pr_l[i]];
    }
}

Применения

Мы уже обсудили, как стек минимумов может помочь нам решить задачу поиска суммы минимумов по всем подотрезкам массива за линейное время. Кроме того, его можно применить для ответа на запросы поиска минимума на отрезке в оффлайн. Далее мы приведем еще несколько примеров задач, в которых стек рекордов может заменить более сложные структуры данных.

Задача: Дан массив $a_0$, $a_1$, $\ldots$, $a_{n - 1}$. Необходимо для каждого индекса $i$ найти количество индексов $j$, таких что $a_j$ не меньше всех элементов, расположенных не дальше от $a_i$ чем $a_j$. Иными словами, количество индексов $j$, таких что не существует индекса $k$, такого что $|k - i| \le |j - i|$ и $a_k > a_j$.

Заметим, что для индекса $i=n-1$ такие индексы $j$ — это в точности элементы стека нестрогих минимумов, потому что для индекса $n-1$ все другие индексы находятся слева, а условие на то, что все ближайшие элементы не меньше данного, как раз эквивалентно условию нахождения в стеке минимумов. Однако для других индексов все не так просто, потому что нас волнуют не только индексы слева, но и справа. Давайте снова перевернем задачу. Вместо того чтобы для индекса $i$ смотреть на все подходящие индексы $j$, мы для каждого индекса $j$ найдем, для каких индексов $i$ он подходит. Во-первых, на отрезке между $i$ и $j$ не должно быть никаких элементов, бóльших $a_j$. То есть, к примеру, $i$ должен быть не левее ближайшего слева числа, большего $a_j$, а также не правее ближайшего справа числа, большего $a_j$. Обозначим таким позиции за $l_0$ и $r_0$, как и раньше. Тогда на самом деле, если есть такой индекс $k$, который ломает желаемые нам условия, то он должен быть равен либо $l_0$, либо $r_0$, потому что все остальные индексы только дальше. Тогда нам надо найти такие индексы $i$, чтобы для них $j$ был ближайшим индексом среди $j$, $l_0$ и $r_0$. Легко понять, что $i$ подходит тогда и только тогда, когда он лежит на отрезке $\left[\left\lceil \frac{l_0 + j + 1}{2} \right\rceil, \left\lfloor \frac{j + r_0 - 1}{2} \right\rfloor\right]$. То есть каждый индекс $j$ добавляет $1$ к ответу для какого-то отрезка индексов $i$, который мы можем легко посчитать, если посчитаем $l_0$ и $r_0$ для всех индексов, используя проходы со стеком максимумов слева направо и справа налево. Теперь нам лишь остается для каждого индекса $i$ понять, сколько отрезков через него проходят. Это можно без труда сделать, используя разностный массив и префиксные суммы. Таким образом, мы решили эту задачу за линейное время, избавившись от использования деревьев отрезков дважды: благодаря стеку максимумов и благодаря разностному массиву.

Задача: Дано число $L$ и два массива положительных целых чисел $h_i$ и $w_i$. Необходимо посчитать значения динамики

$$dp_i = \min_{j < i, w_{j + 1} + w_{j + 2} + \ldots + w_i \le L} dp_j + \max(h_{j + 1}, h_{j + 2}, \ldots, h_i)$$

Это задача с USACO 2012 US Open, Gold Division. Там представлена мотивация для такой странной динамики через легенду про организацию книг в полки с ограничением на ширину, минимизируя суммарную высоту полок.

Как же решать такую задачу? Заметим, что если мы можем упаковать $n$ книг с суммарной высотой полок $H$, то с такой же высотой мы можем упаковать и меньшее количество книг, поэтому $dp$ не убывает. Тогда если для двух индексов $j$ и $k$ значения максимума на отрезках $(j, i]$ и $(k, i]$ равны, то оптимально будет пересчитать динамику через меньший из этих двух индексов. Но максимум на отрезке $(j, i]$ — это как раз таки ближайший справа от $j$ элемент стека максимумов для индекса $i$. И если $j_1$ и $j_2$ — два последовательных индекса в стеке максимумов, таких что через них можно пересчитывать динамику, то среди всех индексов на $[j_1, j_2 - 1]$ оптимально пересчитывать динамику именно через $j_1$, потому что для них всех минимум на отрезке до $i$ равен $h_{j_2}$. Таким образом, практически всегда выгодно пересчитывать динамику через индексы из стека максимумов кроме одной ситуации: если через очередной элемент стека максимумов уже нельзя пересчитать динамику, потому что сумма ширин книг больше $L$. В таком случае мы можем использовать метод двух указателей, чтобы всегда поддерживать самый первый индекс $k$, через который мы все еще можем пересчитываться (используя массив префиксных сумм $w$ или поддерживая сумму ширин на отрезке $(k, i]$). Тогда мы будем поддерживать стек максимумов не как стек, а как дек, удаляя элементы из его начала, если через них уже нельзя пересчитываться, а также рядом со стеком максимумов хранить std::set значений $dp_{j} + h_{j’}$ для каждого элемента стека максимумов $j$, где $j’$ — следующий элемент стека максимумов. Такие значения легко пересчитывать при удалении и добавлении элементов в стек. Тогда для того, чтобы посчитать значение $dp_i$, достаточно взять минимум из минимума значений сета и пересчета через индекс $k$, который мы поддерживаем двумя указателями. Итоговая асимптотика — $O(n \log n)$.

И на самом деле, подобные динамики встречаются во многих других задачах. Ниже даны только несколько примеров задач, которые решаются абсолютно таким же методом. И в целом, стек рекордов — это очень простая и одновременно с этим очень мощная структура данных, которая может сэкономить вам написание дерева отрезков и лишний логарифм в асимптотике во многих задачах.

Источники

Статья о том, что можно использовать стек минимумов без стека минимумов.
Пост про параллельный подсчет ближайшего меньшего слева и справа.

Задачи для практики

Задача на поиск суммы минимумов по всем подотрезкам массива.
Задача с USACO 2012 US Open, Gold Division, разобранная выше.
Задача (спойлеры к петрозаводским сборам), аналогичная последней разобранной задаче выше.
Еще одна задача, аналогичная последней разобранной задаче выше.
Задача, в которой применяется идея, схожая с построением одновременно ближайших слева и справа меньших.
Коллекция задач на стек минимумов.