2426149_re.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 60 行

#include <stdio.h>

int a[100001], max[100001], min[100001], ans[100001][2];

int main()
{
	int l, r, Max, Min;
	int i, n, j, k;

	scanf("%d%d",&n,&k);
	for(i = 0; i < n; i++)
		scanf("%d",&a[i]);
	max[0] = min[0] = -1;
	for(i = 1; i < n; i++)
	{
		j = i-1;
		while(j>=0&&a[j]>a[i])
			j = min[j];
		min[i] = j;
		j = i-1;
		while(j>=0&&a[j]<a[i])
			j = max[j];
		max[i] = j;
	}
	for(i = 0; i <= n-k; i++)
	{
		l = i;r = i+k-1;
		j = r;
		while(1)
		{
			if(max[j]<l)
			{
				Max = a[j];
				break;
			}
			else
				j = max[j];
		}
		j = r;
		while(1)
		{
			if(min[j]<l)
			{
				Min = a[j];
				break;
			}
			else
				j = min[j];
		}
		ans[i][0] = Min;
		ans[i][1] = Max;
	}
	for(j = 0; j < 2; j++)
	{
		for(i = 0; i < n-k; i++)
			printf("%d ",ans[i][j]);
		printf("%d\n",ans[i][j]);
	}
	return 1;
}