：jh輝神說，單調隊列單調棧就是貪心嘛，哎哎，怪自己太無知了！！！！
windows,找出區間的最大最小元素，單調隊列的經典應用嘛。
應該說，貪心的思想，方法，單調隊列是實現的技術才好吧。
poj2832
一次AC，要多理解問題的本質啊！！！
#include<stdio.h>
#include<string.h>
#include<math.h>
int n,k;
int a[1000005],q[1000005];
int main()
{
int i,head,tail;
printf("%d\n",(30<<1)*3);
while (scanf("%d%d",&n,&k)==2)
{
for (i=1; i<=n ; i++)
scanf("%d",&a[i]);
head=1;
tail=0;
memset(q,0,sizeof(q));
for (i=1; i<=n ; i++ )
{
while (head<=tail&&a[q[tail]]>=a[i])
tail--;
tail++;
q[tail]=i;
while (q[head]<=i-k)
head++;
if (i>=k)
printf("%d ",a[q[head]]);
}
printf("\n");
head=1;
tail=0;
memset(q,0,sizeof(q));
for (i=1; i<=n ; i++ )
{
while (head<=tail&&a[q[tail]]<=a[i])
tail--;
tail++;
q[tail]=i;
while (q[head]<=i-k)
head++;
if (i>=k)
printf("%d ",a[q[head]]);
}
printf("\n");
}
return 0;
}
額，這個pascal的代碼好熟悉啊：
var
n,k,i,head,tail:longint;
a,q:array[0..1000001] of longint;
begin
readln(n,k);
for i:=1 to n do
read(a[i]);
head:=1;tail:=0;
for i:=1 to n do
begin
while (head<=tail) and (a[q[tail]]>=a[i]) do dec(tail);
inc(tail);
q[tail]:=i;
while q[head]<=i-k do inc(head);
if i>=k then write(a[q[head]],' ');
end;
writeln;
fillchar(q,sizeof(q),0);
head:=1;tail:=0;
for i:=1 to n do
begin
while (head<=tail) and (a[q[tail]]<=a[i]) do dec(tail);
inc(tail);
q[tail]:=i;
while q[head]<=i-k do inc(head);
if i>=k then write(a[q[head]],' ');
end;
writeln;
end.
居然能沒有pascal???