C++ 基礎題 單調對列

單調對列模板,因為題目的關係所以用 1 開始。

#include<bits/stdc++.h>
using namespace std;

int idx[5000100],nm[5000100];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    stack<int> st;
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>nm[i];
        while(!st.empty() && nm[st.top()]<nm[i]){
            idx[st.top()]=i;
            st.pop();
        }

        st.push(i);
    }

    while(!st.empty()){
        idx[st.top()]=0;
        st.pop();
    }

    for(int i=1;i<=n;i++){
        cout<<idx[i]<<" ";
    }
    return 0;
}

發佈留言