leetcode Min Stack 最小栈

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.

一开始想的简单，只利用一个queue存储：尤其在求最小值得函数里，通过一个for循环找出最小，这是最普通想法，但是很明显当输入数据过多时间复杂度很高：

class MinStack {
private:
vector<int>ss;
public:
    void push(int x) {
		ss.push_back(x);
    }

    void pop() {
		ss.pop_back();
    }

    int top() {
		return ss.at(ss.size()-1);
    }

    int getMin() {
		int min=ss.at(0);
		for(int i=0;i<ss.size();i++)
			if(min>ss.at(i))min=ss.at(i);
	return min;}
};           

换一个思路，要想减小时间复杂度，就通知牺牲空间复杂度，增加另一个栈存储较小值：

class MinStack {
private:
stack<int>ss;
stack<int>ss1;
public:
    void push(int x) {
		if(ss1.empty()||x<=ss1.top())
			ss1.push(x);
		 ss.push(x);
    }

    void pop() {
		if(ss.top()==ss1.top())ss1.pop();
		ss.pop();
    }

    int top() {
		return ss.top();
    }

    int getMin() {
		return ss1.top();}
};