学步园

【题意】

给定n个立方体的高度，求最大矩形面积

【输入】

多组数据，数据以单独一行一个0结束

每组数据一行，第一个数字为n，接下来n个数字表示个立方体的高度

【输出】

对于每组数据，输出一个数表示最大矩形面积

单调栈

从左到右从右到左扫描两次，出栈的时候计算最大面积

很不幸的wa，思路不够全面

program poj2559;
var
  tot,n,i,j,k,s,e:longint;
  now,ans:int64;
  h,stack:array [0..100001] of int64;
begin
  repeat
    read(n);
    if n=0 then break;
    for i:=1 to n do
      read(h[i]);
    ans:=0;
    h[n+1]:=0;
    h[0]:=0;;
    tot:=0;
    stack[0]:=0;
    for i:=1 to n+1 do
      if h[i]>h[stack[tot]] then
        begin
          inc(tot);
          stack[tot]:=i
        end
                             else
        begin
          now:=tot;
          while h[stack[now]]>h[i] do dec(now);
          for k:=now+1 to tot do
            if ans<h[stack[k]]*(stack[tot]-stack[k-1]) then
              ans:=h[stack[k]]*(stack[tot]-stack[k-1]);
          tot:=now;
          inc(tot);
          stack[tot]:=i;
        end;
    tot:=0;
    stack[0]:=n+1;
    for i:=n downto 0 do
      if h[i]>h[stack[tot]] then
        begin
          inc(tot);
          stack[tot]:=i
        end
                             else
        begin
          now:=tot;
          while h[stack[now]]>h[i] do dec(now);
          for k:=now+1 to tot do
            if ans<h[stack[k]]*(stack[k-1]-stack[tot]) then
              ans:=h[stack[k]]*(stack[k-1]-stack[tot]);
          tot:=now;
          inc(tot);
          stack[tot]:=i;
        end;
    writeln(ans);
  until false;
end.