剑指 Offer 30. 包含min函数的栈C++(详解)
C++ 详解 函数 包含 30 Offer min
2023-06-13 09:13:09 时间
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
方法
设置俩个栈,一个数据栈存放数据元素,另一个最小值栈,把最小的值放进去,
1、如果栈为空,直接x同时放入最小值栈和数据栈,
2 、将要放进去的元素与最小值栈的栈顶元素进行比较,如果不满足小于最小值的栈顶,仍然放的是之前的最小值栈的栈顶元素,如果小于则把这个元素放到最小值栈上去
注意(代码的实现方式比较巧妙,如果插入的x大于最小值栈的栈顶元素,那么把此时最小值栈的栈顶元素赋值给x,最终统一的把x放进去就行)
实现代码
class MinStack {
public:
stack<int>_date;
stack<int>_min;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
_date.push(x); //将数据压入数据栈
if(_min.empty()) _min.push(x); //数据栈为空的时候直接插入
else{
if(x > _min.top()) //如果x大于最小栈的栈顶
x = _min.top();
_min.push(x); //将x push进最小的栈
}
}
void pop() { //数据栈与最小栈同时弹出
_date.pop();
_min.pop();
}
int top() {
return _date.top();
}
int min() {
return _min.top();
}
};
相关文章
- C/C++中调用api设置mysql连接的编码方式详解程序员
- 图的存储结构的实现(C/C++实现)详解编程语言
- C++函数的高级特性详解编程语言
- C++中Cstring使用小结详解编程语言
- c++消息队列的实现详解编程语言
- C++之多态性与虚函数详解编程语言
- C++类的继承中构造函数和析构函数调用顺序例子详解编程语言
- C++ normal_distribution高斯正态分布函数用法详解
- C++ discrete_distribution离散分布随机数函数用法详解
- C++函数模板(模板函数)详解
- C++ forward_list用法详解
- C++ set添加、删除和访问(STL set添加、删除和访问)元素详解
- C++ iota函数用法详解
- C++ adjacent_difference相邻差计算方法详解
- C++ showpoint操作符(详解版)
- C++类对象作为函数参数传递详解
- C++ string构造函数和析构函数详解
- C++指针作为函数参数(详解版)
- C++ tellg和tellp函数用法详解
- C++多态和虚函数详解
- 基于C++cin、cin.get()、cin.getline()、getline()、gets()函数的使用详解
- 基于C/C++时间函数的使用详解
- C++类静态成员与类静态成员函数详解
- C++对象的动态建立与释放详解