单调栈结构（进阶） 牛客网

题目描述
给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

输入描述:
第一行输入一个数字 n，表示数组 arr 的长度。

以下一行输出 n个数字，表示数组的值。
输出描述:
输出n行，每行两个数字 L 和 R，如果不存在，则值为-1，下标从0开始。
示例1
输入
复制
7
3 4 1 5 6 2 7
输出
复制
-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

思路：首先构成一个单调栈，放入元素是有3种情况：
（1）栈为空，直接放入
（2）栈不为空，且栈顶元素大于当前放入元素，弹出栈顶元素，继续判断属于那种情况
（3）栈不为空，且栈顶元素小于当前放入元素，直接放入

将所有元素放入后，此时栈是一个从上到下逐渐递减的排列，依次弹出即可。具体细节见代码。

关于，这道题的进阶，放入元素中出现了重复元素，此时单调栈中存放的不再是单一的元素，而是一个list链表，导论情况大致相同，只是，多一种等于栈顶元素时，放入当前栈顶链表。细节见代码，主要难点时stack,与list的配合使用。

 #include<stdio.h>
 #include<stack>
 using namespace std;
 
 
 stack<int> stack_1;
 int arr[1000007];
 int left[1000007];
 int right[1000007];
 
 int main()
 {
 	int n;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)
 	   scanf("%d",&arr[i]);
 	for(int i=0;i<n;i++)
	 {
	 	while( !stack_1.empty() && arr[ stack_1.top() ]>arr[i] )
		 {
		 	int x=stack_1.top();
		 	stack_1.pop();
		 	right[x]=i;
		 	left[x]= stack_1.empty()? -1:stack_1.top(); 
		 }
		 stack_1.push(i);
	 }
	 
	 //现在是一个单调栈，需要将栈中的元素清除
	 
	 while( !stack_1.empty() )
	 {
	 	int x=stack_1.top();
	 	stack_1.pop();
	 	right[x]=-1;
	 	left[x]=stack_1.empty() ? -1:stack_1.top();
	 } 
	 
	 for(int i=0;i<n;i++)
	   printf("%d %d\n",left[i],right[i]); 	
 	return 0;
 } 

题目描述
给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
输入描述:
第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值
输出描述:
输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。
示例1
输入
复制
7
3 4 1 5 6 2 7
输出
复制
-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

 #include<stdio.h>
 #include<stack>
 #include<list>
 using namespace std;
 
 stack< list<int> > stack_1;
 list<int>::iterator it;
  int arr[1000007];
 int left[1000007];
 int right[1000007];
 
 int main()
 {
 	int n;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)
 	  scanf("%d",&arr[i]);
 	
 	for(int i=0;i<n;i++)
	 {
//	 	it=stack_1.top().begin();
	 	while( !stack_1.empty() && arr[ *(stack_1.top().begin() ) ]>arr[i]  )
		 {
		 	 
		 	list<int> mylist;
		 	for( it=stack_1.top().begin(); it!=stack_1.top().end()  ; it++ )
			 	mylist.push_back( *it );//赋值把stack_1.top赋值到mylist中 
		 	stack_1.pop();
		 	for( it= mylist.begin() ; it!=mylist.end() ; it++ )
			 {
			 	right[ *it ]=i;
			 	left[ *it ]= stack_1.empty() ? -1 : *( --stack_1.top().end() );
			 } 
		 }
		 
		 if( !stack_1.empty() && arr[ *(stack_1.top().begin() ) ]==arr[i]  )//当前放入元素和队首相等 
		 {
		 	stack_1.top().push_back( i );
		 }
		 else
		 {
		 	list<int> mylist2;
		 	mylist2.push_back( i );
		 	stack_1.push( mylist2 );
		 }
	 }
	 
	 //此时是一个单调栈结构
	 while( !stack_1.empty() )
	 {
	 	list<int> mylist3;
	 	for( it=stack_1.top().begin() ; it!=stack_1.top().end() ; it++ )
		 	mylist3.push_back( *it );
	 	stack_1.pop();
	 	for( it=mylist3.begin() ; it!=mylist3.end() ; it++  )
		 {
		 	right[ *it ]=-1;
		 	left[ *it ]= stack_1.empty() ? -1 : *( --stack_1.top().end() );
	 		
		 }
	 	
	 } 
 	
 	for(int i=0;i<n;i++)
	   printf("%d %d\n",left[i],right[i]); 
 	
 	
 
 	return 0;
 }