单调栈模型图解入门(HDU1506)

时间:2022-08-01 05:46:42

HDU  1506 面积合并

http://acm.hdu.edu.cn/showproblem.php?pid=1506

单调栈模型图解入门(HDU1506)


很经典的一个题目了。


保持栈非严格单调递增。  


单调栈模型图解入门(HDU1506)

  4号节点来的时候,  3号节点已经无法向右扩展。

 1 、则3号的生命周期结束。  以3号节点高度为矩阵长的 宽度为 (4-3) 。

 2 、同时2号的生命周期结束。  以2号节点高度为矩阵长的 宽度为 (4-2)  ,

        因为2号可以向右扩展到4号的左边。


单调栈模型图解入门(HDU1506)


  2、3节点已死。

 也就是说4号节点可以向左扩展到2号节点,则当4号节点入栈的时候,向左扩展节点标记为2。

单调栈模型图解入门(HDU1506)


5号节点来了。

4号节点无法向右扩展,则4号节点生命周期结束。

以4号节点高度为矩阵长的 宽度为 (5-2)  。

也就是说5号节点可以向左扩展到2(就是4号节点扩展的地方) 。

单调栈模型图解入门(HDU1506)


1号节点无法向右扩展,则1号节点生命周期结束。

以1号节点高度为矩阵长的 宽度为 (5-1)  。

也就是说5号节点可以向左扩展到1(就是1号节点扩展的地方) 。



const int Max_N = 100008 ;

typedef __int64 LL ;

struct Elem{
int id ; //向左扩展最远的下标
LL height ; //当前节点高度
Elem(){}
Elem(int _id , LL _height):id(_id) , height(_height){}
};

struct Stack{
Elem elem[Max_N] ;
int top ;
Stack(){
top = -1 ;
}
void Pop(){
top-- ;
}
bool Empty(){
return top == -1 ;
}
void Push(Elem e){
elem[++top] = e ;
}
Elem Top(){
return elem[top] ;
}
};

LL x[Max_N] ;
int N ;

LL Ans(){
int i , L_id ;
LL ans = 0 ;
Elem e ;
Stack stk ;
for(i = 0 ; i <= N ; i++){
L_id = i ;
while(! stk.Empty() && stk.Top().height > x[i]){
ans = max(ans , (LL)(i - stk.Top().id) * stk.Top().height ) ;
L_id = stk.Top().id ;
stk.Pop() ;
}
stk.Push(Elem(L_id , x[i])) ;
}
return ans ;
}


int main(){
int i ;
while(cin>> N && N){
for(i = 0 ; i < N ; i++)
scanf("%I64d" ,&x[i]) ;
x[N] = -1 ;
cout<<Ans()<<endl ;
}
return 0 ;
}


POJ 3250 

http://poj.org/problem?id=3250

一排共n头牛排队站在一起,给出队伍中每头牛的高度。每头牛只能看到站在他右边且个头比他小的牛。求出所有牛可以看到的牛数之和。

单调栈,严格单调递减。

typedef long long LL  ;

const int Max_N = 100008 ;

int x[Max_N] ;

struct Elem{
int id ;
int height ;
Elem(){}
Elem(int _id , int _height):id(_id) , height(_height){}
};


class Stack{
private :
int top ;
Elem elem[Max_N] ;
public :
Stack(){
top = -1 ;
}
bool Empty(){
return top == -1 ;
}
Elem Top(){
return elem[top] ;
}
void Push(Elem e){
elem[++top] = e ;
}
void Pop(){
--top ;
}
};

int N ;

LL Ans(){
LL ans = 0 ;
int i ;
Stack stk ;
for(i = 1 ; i <= N ; i++){
while(! stk.Empty() && stk.Top().height <= x[i]){
ans += (LL)(i - stk.Top().id - 1) ;
stk.Pop() ;
}
stk.Push(Elem(i , x[i])) ;
}
return ans ;
}

int main(){
int i ;
while(cin>> N){
for(i = 1 ; i <= N ; i++)
scanf("%d" , &x[i]) ;
x[N+1] = 1<<30 ;
N++ ;
cout<<Ans()<<endl ;
}
return 0 ;
}