单调栈(可做模板)

优化版(O(n))

手写栈版

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5000;
int a[N],tt;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int number;
    for (int i = 0; i < n; ++i) {
        cin >> number;
        while (tt && a[tt] >= number) tt--;
        if (!tt) cout << -1 << endl;//特判一下
        else cout << a[tt] << endl;
        a[++tt] = number;
    }
    return 0;
}

调用stack版

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    stack<int>st;
    int number;
    for (int i = 0; i < n; ++i) {
        cin >> number;
        while (!st.empty() && st.top() >= number) {
            st.pop();
        }
        if (st.empty()) cout << -1 << endl;//特判一下
        else cout << st.top() << endl;
        st.push(number);
    }
    return 0;
}