AcWing 41. 包含min函数的栈
原题链接
简单
作者:
小小_88
,
2022-03-05 12:54:34
,
所有人可见
,
阅读 224
包含min函数的栈
C++ 代码
class MinStack {
public:
/** initialize your data structure here. */
int stk[110], tt1; //存储所有元素的栈
int min_stk[110], tt2; //单调栈,栈顶为最小值
MinStack() //初始化
{
tt1 = 0;
tt2 = 0;
}
void push(int x) //添加元素
{
stk[++tt1] = x; //加入栈中
if(!tt2 || x <= min_stk[tt2]) min_stk[++tt2] = x; //如果当前元素不超过单调栈的栈顶元素,加入单调栈中
}
void pop() //弹出栈顶元素
{
if(stk[tt1] == min_stk[tt2]) tt2--; //如果单调栈的栈顶元素和普通栈的栈顶元素相同,一同弹出
tt1--;
}
int top() //返回普通栈的栈顶元素
{
return stk[tt1];
}
int getMin() //返回单调栈的栈顶元素
{
return min_stk[tt2];
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/