1351: 小鱼比可爱Ⅱ求离本小鱼最近的最大或最小元素的下标

一：超时代码，时间复杂度为O（n*n）
```cpp
#include 
using namespace std;
#define base 2333
int A[1000005];
int main()
{
	int n;
	int j;
	scanf("%d",&n);
	for(int i=0;iA[i])
		{
			printf("%d ",j+1);
			break;
		}
		if(j==n)
		printf("0 ");
	}
	
	
	return 0;
}
``

二：正确代码如下，从右往左扫描，维护了一个从栈底到栈顶单调减少的栈

#include 
using namespace std;

int A[1000005];
int B[1000005];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;is;
for(int i=n-1;i>=0;i--)
{
	if(s.empty())
	{
		B[i]=0;
		s.push(i);		
	}
	else
	{
		while(!s.empty()&&A[s.top()]<=A[i])
			s.pop();
		if(s.empty())
		{
			B[i]=0;
			s.push(i);	
		}
		else
		{
			B[i]=s.top()+1;
			s.push(i);
		}
	}
	
}
for(int i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713908.html