白駿2493号:タワー

6757 ワード
stack ps cpp テキストリンク

タワー。


白駿2493号:タワー

アイデア


2つのスタックを作成し、すべてのスタックを1番のスタックにプッシュします.1番スタックのtopと2番スタックのtopを比較します.スタック2番のtopがより大きい場合、またはスタック2番が空の場合、1番スタックから2番スタックにポップアップします.1番スタックのtopがより大きい場合は、2番スタックのpopで、そのインデックスに1番スタックのsizeを記録します.

コード#コード#

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	stack<pair<int, int>> S1, S2;
	int ans[n] = {};
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		pair<int, int> p = {x, i};
		S1.push(p);
	}
	
	while (S1.size()) {
		while (S2.size() && S1.top().first > S2.top().first) {
			ans[S2.top().second] = S1.size();
			S2.pop();
		}
		S2.push(S1.top());
		S1.pop();
	}
	
	for (int i : ans) {
		cout << i << ' ';
	}
    return 0;
}

おしゃべり


C++に変えた理由:かっこいい
STLの使い方について
Java構文とアルゴリズム(BFS)
プリンコード会議