[白俊2493]塔

https://www.acmicpc.net/problem/2493

▼▼初めて近づく

N個のタワーの高さをN回入力してスタックに保存し、現在のスタックの上部の値を上部の下の値と比較し、上部の値が大きい場合、popは上部の値が小さくなるまで保存します.最初のtopの値が現在のtopの値より小さい場合は、インデックスを保存し、前にポップアップした値をスタックに再配置します.
筆者は上記の形式をスタックに繰り返して空にし,結果としてタイムアウトを招いた.スタックを減少させ、増加させる過程で発生する可能性があります.

#include <bits/stdc++.h>
using namespace std;
int main(void){
    int input;
    scanf("%d",&input);
    stack<int> s;
    int res[input], index = 0;
    fill(res, res+input, 0);
    int N = input;
    while(input--) {
        int num;
        scanf("%d",&num);
        s.push(num);
    }

    vector<int> v;
    while(true) {
        int value = s.top();
        int cnt = s.size();
        s.pop();

        while(true) {
            --cnt;
            if(s.empty()) {
                for(int i = v.size()-1; i >= 0; i--) {
                    s.push(v[i]);
                }
                res[index++] = cnt;
                v.clear();
                break;
            }
            if(value > s.top()) {
                v.push_back(s.top());
                s.pop();
            }
            else {
                for(int i = v.size()-1; i >= 0; i--) {
                    s.push(v[i]);
                }
                res[index++] = cnt;
                v.clear();
                break;
            }
        }

        if(index == N) {
            break;
        }
    }

    for(int i = index - 1; i >= 0; i--) {
        printf("%d ",res[i]);
    }

    return 0;
}

▼2度目の接近

スタックに予めN個のタワーの高さを入力して処理するのではなく,入力のたびにプロセスを処理する.stackにすでに値が存在する場合は、現在入力されている値よりもstackに存在する値が大きい場合は、すぐにインデックス値が出力されます.stackが空の場合は最初の入力ですが、それ以前は入力されていなかったので0を出力します.

#include <bits/stdc++.h>
using namespace std;
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, value, index = 0;
    cin >> N;
    stack<int> s;
    int arr[N+1];
    fill(arr,arr+N+1,0);

    for(int i = 0; i < N; i++) {
        cin >> value;
        while(!s.empty()) {
            if(arr[index] >= value) {
                cout << s.top() << ' ';
                break;
            }
            else {
                s.pop();
                --index;
            }
        }
        if(s.empty()) {
            cout << "0 ";
        }
        ++index;
        s.push(i+1);
        arr[index] = value;
    }


    return 0;
}