const maxn=1000005;
var
  a,q,mark:array[0..maxn] of longint; //mark为标记，记录队列中数据的下标
  i,n,k:longint;

procedure getmax(); //区间最大值
var l,r,i:longint;
begin
  l:=1; r:=0;
  for i:=1 to k-1 do //初始化递减队列
    begin
      while (l<=r) and (q[r]<=a[i]) do dec(r);
      inc(r);
      q[r]:=a[i]; mark[r]:=i;
    end;
  for i:=k to n do
    begin
      while (l<=r) and (q[r]<=a[i]) do dec(r);//找a[i]放置的位置
      inc(r);
      q[r]:=a[i];mark[r]:=i;
      while (mark[l]<=i-k) do inc(l); //区间最大值所在位置
      write(q[l],' ');
    end;
  writeln;
end;

procedure getmin(); //区间最小值
var l,r,i:longint;
begin
  l:=1; r:=0;
  for i:=1 to k-1 do //初始化递减队列
    begin
      while (l<=r) and (q[r]>=a[i]) do dec(r);
      inc(r);
      q[r]:=a[i]; mark[r]:=i;
    end;
  for i:=k to n do
    begin
      while (l<=r) and (q[r]>=a[i]) do dec(r);
      inc(r);
      q[r]:=a[i]; mark[r]:=i;
      while (mark[l]<=i-k) do inc(l); //区间队首
      write(q[l],' ');
    end;
  writeln;
end;

begin
  readln(n,k);
  for i:=1 to n do read(a[i]);
  getmin();
  getmax();
end.

• Re:pascal 单调队列代码附上：AC的，耗时有点大，仅供参考 (1205) MathBC 2015-08-28 14:34:18