题解 | #单调栈结构(进阶)#

#include<iostream>
using namespace std;
#include<vector>
#include<stack>
void getAns(vector<int>arr,vector<vector<int>> &ans){
stack<int> s;
for(int i=0;i<arr.size();i++){
	if(!s.empty()){
		if(arr[i]>arr[s.top()]){//当前元素大于栈顶元素，直接压入 
		s.push(i);//注意加的是数组下标 
		}
		else if(arr[i]<=arr[s.top()]){//小于栈顶元素，弹出小于等于arr当前元素的 
			                     //站内元素并收集答案 
		    while(!s.empty()&&arr[s.top()]>=arr[i]){
			   int curIndex=s.top();
			   s.pop();//弹出
			   ans[curIndex][0]=(s.size()==0)?-1:s.top();
			   ans[curIndex][1]=i;
			} 
			s.push(i); 
		}
	}
	else{//栈为空，直接压入 
		s.push(i);
	}
}
while(!s.empty()){//打扫战场 
	int curIndex=s.top();
     s.pop();//弹出
	ans[curIndex][0]=(s.size()==0)?-1:s.top();
} 
for(int i=ans.size()-1;i>=0;i--){
	if(ans[i][1]!=-1){
	if(arr[ans[i][1]]==arr[i]){
		ans[i][1]=ans[ans[i][1]][1];
	} 
	}
}

}
int main(){
	vector<int> arr;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int curNum;
		cin>>curNum;
		arr.push_back(curNum);
	}
	vector<vector<int>> ans(arr.size(),vector<int>(2,-1));
	getAns(arr,ans);
	for(int i=0;i<ans.size();i++){
     cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
	}
	return 0;
}