Следующий больший элемент за O(n): как работает стек и почему амортизация линейна?

В стеке держим индексы элементов, для которых ответ ещё не найден, причём значения в стеке монотонно не возрастают сверху вниз. Идём слева направо. Для нового a[i]: пока на вершине стека элемент, который < a[i], — для него a[i] и есть ближайший больший справа; снимаем его и записываем ответ. Потом кладём i.

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1); // -1 = нет большего справа
    stack<int> st;          // индексы, значения убывают сверху вниз
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = i; // или a[i], если нужно значение
            st.pop();
        }
        st.push(i);
    }
    return res;
}

Сложность O(n) время, O(n) память.

Почему O(n), несмотря на while: каждый индекс кладётся в стек ровно один раз и снимается максимум один раз. Значит суммарное число итераций внутреннего while по всему прогону ≤ n. Это амортизированная оценка: отдельная итерация i может снять много элементов, но «бюджет» удалений ограничен числом добавлений. Для «строго больше» используем <, для «больше либо равно» — <=. Для ближайшего слева — идём с конца или симметрично.