设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

题目：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

pop、top和getMin操作总是在非空栈上调用。

思路：

1. 预设两个栈，左边栈负责接收元素，右边栈负责存最小元素
2. 元素入左边栈，入栈时比较左右栈顶元素，如果新元素小，把新元素放在右边的栈顶位置，如果新元素大，则把右边栈顶元素还放在栈顶的位置
3. 出栈时，出入栈的最后一个元素，也就是左边栈顶元素
4. 出最小值时，出右边栈顶元素
5. 出栈时两个都得出

代码：

Java：

class MinStack {
public:
	/** initialize your data structure here. */
	MinStack() {

	}

	void push(int x) {
	    left.push(x);
		if (right.empty() || x <= right.top()){
			right.push(x);
		}
	}

	void pop() {
        int top = left.top();  //先让左边出栈并记录元素
		left.pop();    		
		if (top == right.top()){  //如果左边出栈得元素等于右边栈顶元素，右边才出
			right.pop();
		}
	}

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

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

	stack<int> left;  //存原始数据
	stack<int> right;  //存最小数据
};

python（列表）：

class minstack :

def __init_( self):

    self.nums = []

def push(self, x: int) ->None:

    self.nums.append(x)

def pop( self) - > None :

    self.nums.pop( -1)

def top( self) -> int:

    return self.nums[ -1]

def getMin(self) -> int:

    return min( self.nums)

python（栈）：

class Minstack :

def _init_(self):

    self.nums = []
    self.minnum = None

def push(self,x: int) ->None:

    self.nums.append(x)
    if self.minnum is None or self.minnum > x:
        self.minnum = x

def pop( self) -> None:

    x = self.nums.pop( -1)
    if self.minnum == x:
        if len( self.nums) >=1:
            self.minnum = min( self.nums )
        else:
            self.minnum = None

def top(self) -> int:

    return self. nums[-1]

def getMin(self) -> int:

    return self.minnum