鉄則本 A60 - Stock Price (2Q, ★4)

スタックを用いて解決できる典型問題

• 問題へのリンク

問題概要

長さ の数列 が与えられる。

各 に対して、 かつ を満たす最大の を求めよ (存在しない場合は -1)。

制約

• 

メモ

スタックを使うと の計算量で解ける。詳細は鉄則本を参照。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, A;
    cin >> N;

    vector<pint> stk;
    for (int i = 0; i < N; i++) {
        cin >> A;
        while (!stk.empty() && stk.back().first <= A) stk.pop_back();
        if (stk.empty()) cout << -1 << " ";
        else cout << stk.back().second+1 << " ";
        stk.emplace_back(A, i);
    }
    cout << endl;
}