实现一个获取栈中最小数据成员的函数，该栈支持如下操作： 1.push(x) : 将元素x压入栈中 2.pop() : 弹出(移除)栈顶元素 3.top() : 返回栈顶元素 4.getMin() : 返回栈内最小元素 要求时间复杂度为O(1)
这里关键是如何获取最小值，栈中的元素不断增加，且要达到O（1）常数级的时间复杂度，即创建好的栈进行排序，返回最小值是不可行的。
这里只有在创建过程中将栈中的最小值获取到，此时一个可行的办法为： 维护一个最小栈，保持栈顶元素为所有元素的最小值，且大小与原本数据栈保持一致。 这样即使有原本数据的删除添加，最小栈同样跟随数据删除添加即可。 方法一（一个栈）： 数据结构实现如下:
void push(int x) { data_stack.push(x); /*当最小栈中的元素不为空的时候，和栈顶元素进行大小比较，判断是否要入栈*/ if (!min_stack.empty()) { if (min_stack.top() > x) { min_stack.push(x); } else { min_stack.push(min_stack.top()); } } /*为空的时候即可入栈*/ else { min_stack.push(x); } } /*此时最小栈的栈顶即为数据栈中的最小元素*/ int get_min(){ return min_stack.top(); }方法二（两个栈）：
class MinStack { stack<int> S; int min=2147483647; public: /** initialize your data structure here. */ MinStack() { } //push操作 void push(int x) { if (x <= min) { //当遇到小于等于最小值的数值，将上一个最小值也push到栈中 S.push(min); min = x; } S.push(x); } void pop() { if (S.top() == min) { //pop的时候发现pop的时最小值，那么pop两次，同时变更最小值 S.pop(); min = S.top(); S.pop(); } else { S.pop(); } } int top() { return S.top(); } int getMin() { return min; } };测试代码实现如下:
#include <stack> #include <iostream> #include <algorithm> using namespace std; class My_stack{ private: stack<int> data_stack,min_stack; public: void push(int x) { data_stack.push(x); if (!min_stack.empty()) { if (min_stack.top() > x) { min_stack.push(x); } else { min_stack.push(min_stack.top()); } } else { min_stack.push(x); } } void pop() { min_stack.pop(); data_stack.pop(); } int top() { return data_stack.top(); } int get_min(){ return min_stack.top(); } }; int main(){ My_stack s; int tmp; cout << "construct the stack " << endl; while(cin >> tmp) { s.push(tmp); } cout << "min is " << s.get_min() << endl; s.pop(); cout << "after pop " << s.top() << endl; s.push(-4); cout << "after push ,the top and min is " << s.top() << " " << s.get_min() << endl; return 0; }输出如下:
construct the stack 2 -1 -3 2 0 4 d min is -3 after pop 0 after push -4,the top and min is -4 -4