stack<pair<int, int>> sta;
void push(int x) {
int min_i;
if(sta.empty())
{
min_i = x;
}
else
{
min_i = sta.top().second < x ? sta.top().second : x;
}
sta.push({x, min_i});
} void pop() {
sta.pop();
} int top() {
return sta.top().first;
} int getMin() {
return sta.top().second;
}
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)