《剑指offer》 包含min函数的栈

时间:2021-06-02 00:27:52

本题来自《剑指offer》 包含min函数的栈

题目:

  定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

思路:

  举例子让抽象问题具体化。

C++ Code:

class Solution {
private:
stack<int> m_data; //数据栈
stack<int> m_min; //辅助栈,存放较小的数据
public:
void push(int value) {
m_data.push(value); //刚进来就要把数据存放在数据栈中
if(m_min.size()==||value<m_min.top()){ //如果其值小于数据栈中的栈顶,则将其放入到辅助栈中
m_min.push(value);
}else{
m_min.push(m_min.top()); //否则辅助栈中继续存入辅助栈中最小的元素
}
}
void pop() {
m_data.pop(); //数据栈出栈顶
m_min.pop(); //辅助栈出栈顶
}
int top() {
return m_min.top(); //返回最小栈中的栈顶
}
int min() {
return m_min.top(); //返回辅助栈最小数据即栈顶元素
}
};