[C++知识库]百亿富翁（单调栈）

题目描述

已知这排楼房一共有 $N$ 栋，编号分别为 $1～N$，第 $i$ 栋的高度为 $h_i$

好奇的小明想知道对于每栋楼，左边第一个比它高的楼房是哪个，右边第一个比它高的楼房是哪个（若不存在则输出 $?1$）。
百亿富翁（单调栈）

C++(单调栈)

首先想到暴力解法，直接写两个for循环。

但这道题数据量为$10^5$，所以要想一个时间复杂度$O(nlogn)$的解法。

拿左边第一个比它高的楼盘来说，我们可以维护一个单调栈来处理这一过程。当扫到一个数时，如果此时栈顶的元素比当前元素还小的话，那必然不可能是后续数据的答案，因为这里要找的是左边第一个比它高的楼盘，就可以令栈顶元素出栈。

#include <iostream>
#include <cstdio>
#define x first
#define y second
using namespace std;
const int N = 7e5 + 10;
typedef pair<int, int> PII;
PII stk[N], a[N];
int tt;
int rightans[N];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		a[i] = {x, i};
	}
	// 左边第一个比它高
	for (int i = 1; i <= n; i++) {
		while (tt && stk[tt].x <= a[i].x) tt--;
		if (tt) cout << stk[tt].y << ' ';
		else cout << -1 << ' ';
		stk[++tt] = a[i];
	} 
	cout << endl;
	tt = 0;
	// 右边第一个比它高
	for (int i = n; i > 0; i--) {
		while (tt && stk[tt].x <= a[i].x) tt--;
		if (tt) rightans[i] = stk[tt].y;
		else rightans[i] = -1;
		stk[++tt] = a[i];
	} 
	for (int i = 1; i <= n; i++) cout << rightans[i] << ' ';
	
	return 0;
}