1.题目解析

本题是实现一个栈并且要实现其中的插入、删除、返回栈顶元素、返回最小元素的函数，这里主要的难点就是返回最小元素的函数，如果我们直接遍历，那么时间复杂度就是O(N)，但是题目要求我们需要在常数时间也就是O(1)的时间复杂度内实现，那么接下来我们使用一种巧妙地方法来完成本题

 

2.算法原理

这里的主要难点只有在常数时间内找出栈顶最小元素，我们可以创建一个minst栈来存储数据，具体原理是在向st插入数据时判断此时插入的数据与minst中的栈顶元素哪个更小，如果minst的栈顶元素更小则st继续插入，反之则将该较小值插入minst的栈顶即可，注意重复数字也需要插入，因为st删除数据时如果此时st与minst的栈顶元素相同则需要同时删除，最后minst栈顶的元素就是st栈中的最小值，此时直接返回minst.top()即可

 

3.代码展示

class MinStack {
public://构造函数可以直接使用默认构造//这里可以保留也可以直接删除，因为//最后都会执行默认构造函数，析构也是如此MinStack() {}//插入原栈同时判断是否需要插入最小数据的栈void push(int val) {st.push(val);if(minst.empty() || minst.top() >= val){minst.push(val);}}//删除原栈元素同时删除最小栈中对应元素void pop() {if(minst.top() == st.top()){minst.pop();}st.pop();}int top() {return st.top();}int getMin() {return minst.top();}private:stack<int> st;stack<int> minst;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/