【Data Structures】Something About Monotone Queue/Stack

单调队列和单调栈的本质思想都是通过问题或者问题结果的单调性来找出极值性的答案。

【Poj 2559】Largest Rectangle in a Histogram

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h₁,...,h_n, where 0<=h_i<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

【Solution】

维护一个单调的队列，通过单调性的判断和维护来处理出每一个点的左右扩展的极值长度。

具体操作的，就是让每一个节点入队（队列单调递增），把队列中大于等于它的都删去，因为大于等于加入节点的都是没有价值的，或者说新加入的节点的价值包含他们的价值。（比如8 5两个节点，之后的节点，如果小于等于5，那么也一定小于等于8，如果大于5，那么它向左必然不能扩展到5这个节点，更别说8了）

【Code】

  1: Program Poj_2559(input,output);
  2:   var que,a,left,right:array[0..100005] of longint;
  3:       n,i,j,k,tail:longint;
  4:       ans:int64;
  5:   function max(a,b:int64):int64;
  6:     begin if a>b then exit(a) else exit(b);end;
  7:   begin
  8:     read(n);
  9:     while n<>0 do
 10:       begin
 11:         for i:=1 to n do read(a[i]);
 12:         tail:=1;que[1]:=0;a[0]:=-1;
 13:         for i:=1 to n do
 14:           begin
 15:             while(tail>0)and(a[que[tail]]>=a[i])do dec(tail);
 16:             left[i]:=que[tail]+1;
 17:             inc(tail);que[tail]:=i;
 18:            end;
 19:         tail:=1;que[1]:=n+1;a[n+1]:=-1;
 20:         for i:=n downto 1 do
 21:           begin
 22:             while(tail>0)and(a[que[tail]]>=a[i])do dec(tail);
 23:             right[i]:=que[tail]-1;
 24:             inc(tail);que[tail]:=i;
 25:           end;
 26:         ans:=0;
 27:         for i:=1 to n do
 28:           ans:=max(ans,int64(right[i]-left[i]+1)*int64(a[i]));
 29:         writeln(ans);
 30:         read(n);
 31:       end;
 32:     end.

【Poj 2452】Sticks Problem

Description

Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line, represented by S1, S2, S3, ...Sn. After measuring the length of each stick Sk (1 <= k <= n), she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed between Si and Sj is longer than Si but shorter than Sj.
Now given the length of S1, S2, S3, …Sn, you are required to find the maximum value j - i.

Input

The input contains multiple test cases. Each case contains two lines.
Line 1: a single integer n (n <= 50000), indicating the number of sticks.
Line 2: n different positive integers (not larger than 100000), indicating the length of each stick in order.

Output

Output the maximum value j - i in a single line. If there is no such i and j, just output -1.

Sample Input

4
5 4 3 6
4
6 5 4 3

Sample Output

1
-1

【Solution】

题目大意是对一个数列找到一个满足区间左端点是区间最小值，右端点是区间最大值（最大值不等于最小值）的最长区间。

我的解法是用单调栈处理出一个Right数组，Right[i]表示第i个节点右边最后一个比它大的数字的编号，效率为O（N）。

那么问题就变成了从区间[i,Right[i]]中寻找最大的数字，让它和编号为i的数字组成所求区间（Rmq问题），这样用St去做，O（NlogN）的效率即可。

题目有一点XD的地方在于你开[50000]的数组是RE的，我开到[100000]就AC了..（0.0）

【Code】

  1: Program Poj2452(input,output);
  2:   var F,G:array[1..50000,0..16]of longint;
  3:       que,a,right:array[1..50001]of longint;
  4:       tail,i,n,t,j,tmp,ans,k:longint;
  5:   Function max(a,b:longint):longint;
  6:     begin if a>b then exit(a) else exit(b);end;
  7:   Function Ask(x,y:longint):longint;
  8:     begin
  9:       if x=y then exit(x)
 10:       else
 11:         begin
 12:           k:=trunc(ln(y-x+1)/ln(2));
 13:           if F[y-1<<k+1,k]>F[x,k] then exit(G[y-1<<k+1,k]) else exit(G[x,k]);
 14:         end;
 15:     end;
 16:   begin
 17:     while not eof do
 18:       begin
 19:         readln(n);
 20:         fillchar(a,sizeof(a),0);
 21:         fillchar(F,sizeof(F),0);
 22:         fillchar(Right,sizeof(Right),0);
 23:         fillchar(G,sizeof(G),0);
 24:         fillchar(que,sizeof(que),0);
 25:         for i:=1 to n do read(a[i]);readln;
 26:         a[n+1]:=-1;que[1]:=n+1;tail:=1;
 27:         for i:=n downto 1 do
 28:           begin
 29:             while(tail>0)and(a[que[tail]]>=a[i])do dec(tail);
 30:             Right[i]:=que[tail]-1;
 31:             inc(tail);que[tail]:=i;
 32:           end;
 33:         for i:=1 to n do begin F[i,0]:=a[i];G[i,0]:=i;end;
 34:         t:=trunc(ln(n)/ln(2));
 35:         for j:=1 to t do
 36:           for i:=1 to n do
 37:             if i+-1<=n then
 38:               begin
 39:                 F[i,j]:=F[i,j-1];G[i,j]:=G[i,j-1];
 40:                 if F[i+1<<(j-1),j-1]>F[i,j] then
 41:                   begin
 42:                     F[i,j]:=F[i+1<<(j-1),j-1];
 43:                     G[i,j]:=G[i+1<<(j-1),j-1];
 44:                   end;
 45:               end
 46:             else break;
 47:         ans:=-1;
 48:         for i:=1 to n do
 49:           begin
 50:             tmp:=Ask(i,Right[i]);
 51:             if tmp-i>ans then ans:=tmp-i;
 52:           end;
 53:         if ans=0 then writeln(-1) else writeln(ans);
 54:       end;
 55:   end.