[伯俊]17298号:ああ、大数

Ai8は4の整数なので、出力アレイに追加できます.

stack.top()によると、8は5の5大数です.そして5の5つの数を見つけて、5をスタックから取り出します.

9は8より大きいので、8は9の整数ではありません.その後、Ai8は最後の要素であるため、大きな整数は存在しないので、大きな整数-1を処理することができる.

📕 Code

#include <iostream>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

vector<int> nums(1'000'001);
vector<int> answer(1'000'001);

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;  cin >> n;
    for(int i=0; i<n; i++)
        cin >> nums[i];

    stack<pair<int, int>> st;	// Ai와 idx를 저장할 스택
    for(int i=0; i<n-1; i++)
    {
        if(nums[i] < nums[i+1])	// A[i] < A[i+1] 이면 오큰수를 찾음
        {
            answer[i] = nums[i+1];	// 오큰수 저장
            while(!st.empty() && st.top().first < nums[i+1])
            {		// 스택에 저장된 오큰수를 찾지 못한 원소들을 하나씩 꺼내어 
            		// A[i+1] 이 오큰수가 되는 지 비교
                answer[st.top().second] = nums[i+1];	// 오큰수가 된다면 추가!
                st.pop();	// 오큰수를 찾았으므로 pop!
            }
        }
        else
            st.push(make_pair(nums[i], i));	// A[i] >= A[i+1] 이면 
            					// 오큰 수를 찾지 못했으므로 
 		                                // 스택에 저장!
    }
    st.push(make_pair(nums[n-1], n-1));		// 마지막 원소는 오큰수가 없으므로 스택에 저장

    while(!st.empty())		// 마지막 원소까지 비교했음에도 불구하고 
    				// 오큰수를 찾지 못한 원소들은
    {
        answer[st.top().second] = -1;	// -1 처리
        st.pop();
    }

    for(int i=0; i<n; i++)
        cout << answer[i] << ' ';

    return 0;
}

📕 ポスト