单调队列和单调栈的本质思想都是通过问题或者问题结果的单调性来找出极值性的答案。
【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 h1,...,hn, where 0<=hi<=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 0Sample 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 do10: 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 do14: 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 do21: 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 do28: 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 3Sample 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 do18: 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 do28: 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 do36: for i:=1 to n do37: if i+-1<=n then38: 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] then41: 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 do49: 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.