C++ 基礎題 單調對列

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

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

int idx[5000100],nm[5000100];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    //freopen("test.txt","r",stdin);  測試用
    //freopen("ans.txt","w",stdout);
    stack<int> st;//index
    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;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *