假设我们要制作一个最大的堆栈，它支持以下操作-
MaxStk() 这将构造一个最大堆栈的新实例
push(val) 将val插入堆栈
top() 从堆栈中获取最高的元素
max() 从堆栈中获取最大元素
pop() 从堆栈中删除并返回最上面的元素
popmax() 从堆栈中删除并返回最大元素
现在通过调用构造的最大堆栈MasStk()，然后推像5,15，10，然后调用三个值top()，max()，popmax()，max() pop()，top()分别功能。那么初始堆栈状态将为[5、15、10]，以及该功能的相应输出：10、15、15、10、10、5
为了解决这个问题，我们将遵循以下步骤-
pos_index：= 0
定义一个set stk另一个set aux
定义构造函数，这没有做任何特殊的任务
定义一个函数push()，将需要val，
将pos_index，val插入stk
将val，pos_index插入aux
（将pos_index增加1）
定义功能 top()
如果stk为空，则-
返回-1
返回stk的第一项的第二个值
定义功能 max()
如果aux为空，则-
返回-1
返回aux的第一项的第一个值
定义功能 pop()
如果stk为空，则-
返回-1
id：= stk的第一项的第一个值，ret = stk的第一项的第二个值
从stk删除stk的第一个元素
从aux删除对(ret,id)
返回ret
定义功能 popmax()
如果aux为空，则-
返回-1
ret：= aux的第一项的第一个值，id = aux的第一项的第二个值
从aux删除aux的第一个元素
pair(id, ret)从stk删除
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class MaxStk {
int pos_index = 0;
set<pair<int, int>, greater<>> stk, aux;
public:
MaxStk() {}
void push(int val) {
stk.emplace(pos_index, val);
aux.emplace(val, pos_index);
pos_index++;
}
int top() {
if (stk.empty())
return −1;
return stk.begin()−>second;
}
int max() {
if (aux.empty())
return −1;
return aux.begin()−>first;
}
int pop() {
if (stk.empty())
return −1;
int id = stk.begin()−>first, ret = stk.begin()−>second;
stk.erase(stk.begin());
aux.erase({ret, id});
return ret;
}
int popmax() {
if (aux.empty())
return −1;
int ret = aux.begin()−>first, id = aux.begin()−>second;
aux.erase(aux.begin());
stk.erase({id, ret});
return ret;
}
};
int main(){
MaxStk max_stk;
max_stk.push(5);
max_stk.push(15);
max_stk.push(10);
cout << max_stk.top() << endl;
cout << max_stk.max() << endl;
cout << max_stk.popmax() << endl;
cout << max_stk.max() << endl;
cout << max_stk.pop() << endl;
cout << max_stk.top() << endl;
}max_stk.push(5) max_stk.push(15) max_stk.push(10) max_stk.top() max_stk.max() max_stk.popmax() max_stk.max() max_stk.pop() max_stk.top()输出结果
10 15 15 10 10 5