leecode 解题总结：155. Min Stack

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <stack>using namespace std;/*问题:Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.push(x) -- Push element x onto stack.pop() -- Removes the element on top of the stack.top() -- Get the top element.getMin() -- Retrieve the minimum element in the stack.Example:MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> Returns -3.minStack.pop();minStack.top();      --> Returns 0.minStack.getMin();   --> Returns -2.分析:最小栈。设计一个栈，支持在常量时间内返回最小元素。这是程序员面试金典的题目。记得好像使用一个栈，每次遇到将当前元素与栈顶元素中的最小值插入其中。-2 0 -3 -3 2 2 4 3最小栈为空：插入-2,0与-2比较，-2较小，继续插入-2，-2与-3比较，-3较小，插入-3对2 2 4 3最小值一直为-3，不插入得到minStack值为:-2 -3要获取最小元素的时候，发现当前栈顶元素为3，弹出最小栈的栈顶-3.并将-3弹出。如果正常栈的栈顶元素 != 最小栈的栈顶元素，获取最小栈的栈顶元素；否则，输出最小栈的栈顶元素，并弹出最小栈的栈顶元素。最小栈维护了当前标准栈的最小值输入:5(输入的元素个数) 13(指令个数)-2 0 -3 -3 2 push 3getMin popgetMinpopgetMinpopgetMinpopgetMinpopgetMinpop输出:-3-3-3-3-2-2关键：1 设定标准栈用于完全模拟正常情况，设定最小栈，当待插入元素 <= 最小栈的栈顶元素，则在最小栈中插入该元素；pop时，如果标准栈的栈顶元素=最小栈的栈顶元素，则一起pop，否则，只pop标准栈*/class MinStack {public:    /** initialize your data structure here. */    MinStack() {    }        void push(int x) {        _normalStack.push(x);		if(!_minStack.empty())		{			//比较当前元素和最小栈的栈顶元素，如果当前元素=最小栈的栈顶元素，压入元素			if(x <= _minStack.top())			{				_minStack.push(x);			}		}		else		{			_minStack.push(x);		}    }    	//弹出元素，弹出栈顶元素时，如果栈顶元素=最小栈栈顶元素，则一起弹出，否则继续处理    void pop() {		if(_normalStack.empty() || _minStack.empty())		{			return;		}		int value = _normalStack.top();		_normalStack.pop();		//两者相等，弹出最小栈的栈顶元素		if(value == _minStack.top() )		{			_minStack.pop();		}    }    	//返回栈顶元素，返回正常栈的栈顶元素    int top() {		if(!_normalStack.empty())		{			return _normalStack.top();		}		else		{			return 0;		}    }    	//获取最小元素    int getMin() {		if(!_minStack.empty())		{			return _minStack.top();		}		else		{			return 0;		}    }PRivate:	stack<int> _minStack;	stack<int> _normalStack;//标准栈};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 vector<int> result;	 int commandNum;	 string command;	 while(cin >> num >> commandNum )	 {		 MinStack minStack;		 //nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 minStack.push(value);		 }		 for(int i = 0 ; i < commandNum ; i++)		 {			 cin >> command;			 if("push" == command)			 {				 cin >> value;				 minStack.push(value);			 }			 else if("pop" == command)			 {				 minStack.pop();			 }			 else if("getMin" == command)			 {				 cout << minStack.getMin() << endl;			 }		 }	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}