第十九题：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：利用一个辅助栈来存放最小值
栈 3，4，2，5，1
辅助栈 3，3，2，2，1
每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈顶，当出栈时，辅助栈也要出栈
栈入3， 辅助栈入3，
栈入4，辅助栈栈顶比4小入3，
栈入2，辅助栈栈顶是3比2大所以入2，每次都是把栈顶与入栈的值比较，入那个最小的，这样栈顶一直最小。
Python：
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.minstack = []
def push(self, node):
# write code here
self.stack.append(node)
if self.minstack == [] or node < self.min():
self.minstack.append(node)
else:
self.minstack.append(self.min())
def pop(self):
# write code here
if self.minstack == [] or self.stack == []:
return None
self.minstack.pop()
self.stack.pop()
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.minstack[-1]
Java:
import java.util.Stack;
public class Solution {
Stack<Integer> stck = new Stack<>();
Stack<Integer> min_stck = new Stack<>();//辅助栈，栈顶存放当前stck中最小值
public void push(int node) {
stck.push(node);
if(min_stck.empty())
min_stck.push(node);
else if(node < (int)min_stck.peek())
min_stck.push(node);
else
min_stck.push(this.min());
}
public void pop() {
stck.pop();
min_stck.pop();
}
public int top() {
return (int)stck.peek();
}
public int min() {
return (int)min_stck.peek();
}
}
