这道题目很简单,只是一道栈的模拟题。至于最大值,我们可以用平衡树来维护。

操作:

  • 操作0:把XX压入栈,并插入到平衡树中;
  • 操作1:从平衡树中删除栈顶元素,并从栈中弹出栈顶元素;
  • 操作2:查找平衡树中最大元素(一直往右子树找,没有右子树了就返回);

于是我们就愉快地解决了。

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<stack>
using namespace std;
struct nodes{
	int rd,x,lc,rc,cnt;
	nodes(int X){
		lc=rc=0;
		x=X;
		rd=rand();
		cnt=1;
	}
	nodes(){
		lc=rc=0;
		x=0;
		cnt=0;
	}
};
nodes node[200001];
int root,cnt;
int newNode(int x){
	node[cnt++]=nodes(x);
	return cnt-1;
}
void zig(int x,int f){
	int temp=node[node[x].lc].rc;
	node[node[x].lc].rc=x;
	if(x==root)root=node[x].lc;
	else{
		if(node[f].lc==x){
			node[f].lc=node[x].lc;
		}else node[f].rc=node[x].lc;
	}
	node[x].lc=temp;
}
void zag(int x,int f){
	int temp=node[node[x].rc].lc;
	node[node[x].rc].lc=x;
	if(x==root)root=node[x].rc;
	else{
		if(node[f].lc==x){
			node[f].lc=node[x].rc;
		}else node[f].rc=node[x].rc;
	}
	node[x].rc=temp;
}
void insert(int &nd,int f,int x){	//插入
	if(nd==0){
		nd=newNode(x);
		return;
	}
	if(x<node[nd].x){
		insert(node[nd].lc,nd,x);
		if(node[node[nd].lc].rd>node[nd].rd){
			zig(nd,f);
		}
	}else if(x>node[nd].x){
		insert(node[nd].rc,nd,x);
		if(node[node[nd].rc].rd>node[nd].rd){
			zag(nd,f);
		}
	}else{
		node[nd].cnt++;
	}
}
void del(int &nd,int f,int x){	//删除
	if(node[nd].x==x){
		if(node[nd].cnt>1){
			node[nd].cnt--;
			return;
		}
		if(node[nd].lc+node[nd].rc==0){
			nd=0;
			return;
		}
		if(node[nd].lc==0){
			int t=node[nd].rc;
			zag(nd,f);
			del(nd,t,x);
			return;
		}
		if(node[nd].rc==0){
			int t=node[nd].lc;
			zig(nd,f);
			del(nd,t,x);
			return;
		}
		if(node[node[nd].lc].rd>node[node[nd].rc].rd){
			int t=node[nd].lc;
			zag(nd,f);
			del(nd,t,x);
		}else{
			int t=node[nd].rc;
			zig(nd,f);
			del(nd,t,x);
		}
	}else{
		if(x<node[nd].x){
			del(node[nd].lc,nd,x);
		}else{
			del(node[nd].rc,nd,x);
		}
	}
}
int query(int nd){	//查询
	if(node[nd].rc==0){
		return node[nd].x;
	}else return query(node[nd].rc);
}
stack<int> sta;
int main(){
	int n;
	root=newNode(0);
	scanf("%d",&n);
	while(n--){
		int x,y;
		scanf("%d",&x);
		if(x==0){
			scanf("%d",&y);
			insert(root,0,y);
			sta.push(y);
		}else if(x==1){
			if(sta.empty())continue;
			del(root,0,sta.top());
			sta.pop();
		}else{
			if(sta.empty())puts("0");
			else printf("%d\n",query(root));
		}
	}
}

如果你看懂了,恭喜你;如果没看懂,没关系,还有另一种做法。毕竟这是一道入门题。

思考:难道栈中存的一定是输入的内容吗?

未必。

我们发现,当压入的一个数XX不比之前栈中所有数大的时候,它的压入与弹出对栈内数的最大值是没有任何影响的。

为什么呢?因为比XX之前入栈的一些数中有比它大的数。要想让XX成为栈中的最大数,就必须把比它之前入栈的所有比它大的数都弹出去。由于题目要求只能入栈一次,所以以上操作显然违背了栈的定义。

XX大于之前栈中所有的数的时候,它的压入与弹出对栈内数的最大值有影响,但对之前栈内的最大值无影响。

所以我们栈中存的数据是在入库之后仓库内所有集装箱的最大重量。

代码:

#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
stack<int> sta;
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		int x,y;
		scanf("%d",&x);
		if(x==0){
			scanf("%d",&y);
            if(sta.empty())sta.push(y);
			else sta.push(max(sta.top(),y));
		}else if(x==1){
			if(sta.empty())continue;
			sta.pop();
		}else{
			if(sta.empty())puts("0");
			else printf("%d\n",sta.top());
		}
	}
}
2020 01 19 Sun 11:28:00
2020 10 17 Sat 07:00:25