i706 - B.永遠ㄉ神（yyds）

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個包含 n 個人身高的序列，要求對於每個人的身高，找到其前面最靠近且身高比自己矮的人的編號。如果前面沒有比自己矮的人，則輸出 0。

解題思路

本題可以使用單調棧 (Monotonic Stack) 來有效率地解決。單調棧維持一個遞增或遞減的序列，可以快速找到滿足條件的元素。

具體來說，我們使用一個棧來儲存已經遍歷過的人的身高和編號。對於當前的人，我們從棧頂開始比較，直到找到一個比當前人矮的人，或者棧為空。如果找到比當前人矮的人，則輸出該人的編號。如果棧為空，則輸出 0。

在遍歷完當前人後，將其身高和編號壓入棧中。為了維持棧的單調性，在壓入之前，需要將棧中所有比當前人高的元素彈出。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
pair <long,long> stk[1000001];//v it
int x,sz=1;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> x;
		while(x<=stk[sz-1].first)sz--;
		cout << stk[sz-1].second << " ";
		stk[sz++]={x,i};
	}
}