农村的阿牛非常喜欢养牛，他想设计一个数据结构来存储他的牛，每头牛都有一个不同的编号和对应的体重。阿牛希望可以在常数时间内得到最重的一头牛的体重，还能随时加入、删除和查询牛的信息。你能帮助阿牛设计这个数据结构吗？ 题目描述： 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最大权值的牛的体重的数据结构。 实现 MaxCowStack 类： MaxCowStack() 初始化堆栈对象。 void push(int id, int weight) 将编号为 id 且体重为 weight 的牛推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的体重。 int getMax() 获取最重一头牛的体重。
示例1

输入

["MaxCowStack","push","push","push","getMax","pop","top","getMax"],[[],[1,2],[2,3],[3,1],[],[],[],[]]

输出

[-1,-1,-1,-1,3,-1,3,3]

说明

前四个操作没有获取元素，用-1占位，并连续将三个元素加入到栈中；然后获取最大值3；弹出栈顶元素，继续用-1占位；然后获取栈顶元素3；最后获取最大值3.

备注:
op数组中的字符串表示各种操作：MaxCowStack表示创建栈；push表示加入栈中；pop表示从栈中弹出元素；top表示获取栈中元素；getMax表示获取栈中元素最大值；前三个操作后的结果都用-1占位，后两个操作得到相应的结果。val数组，val[i].size() = 2，val[i][0]表示牛的编号，val[i][1]表示牛的体重1 pop、top 和 getMax 操作总是在 非空栈 上调用push, pop, top, and getMax最多被调用 3 * 10^4 次
加载中...