Author: loop3r
Date: 20251013
tag: 单调栈
link: https://www.luogu.com.cn/problem/P5788

题目描述

link

分析

略

代码实现

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 3e6 + 10;
int n, a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];

	vector<int> res;
	stack<PII> st;
	for (int i = n; i >= 1; i--) {
		while (st.size() && st.top().first <= a[i]) {
			st.pop();
		}
		if (st.empty()) res.push_back(0);
		else res.push_back(st.top().second);
		st.push({a[i], i});
	}

	for (int i = res.size() - 1; i >= 0; i--) cout << res[i] << " ";
	cout << endl;

	return 0;
}