题目

设计包含min 函数的栈。
定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。

个人解题思路

1.存储结构采用数组

2.min函数的添加：主要是每次push元素的时候，都要进行比较，保存最小的元素。所以里面要有一个保存最小元素的属性，用什么来存很关键。当你pop的元素刚好是最小元素的时候，需要将最小元素改为上一次最小的数，所以这个时候就得保存每次比较后最小的元素。所以需要一个集合来保存，该集合的元素是从大到小排列好的，而且更具第一条，我们得使用数组的顺序存储结构，所以这里我们采用包装数组ArrayList来保存。

第一次，最小的数为本身，放入到list集合中。当第i次push的时候（i>2），要比较该元素和栈中最小元素，如果小于等于该数，就将该元素添加到list中。当pop的数刚好是最小的元素的时候，list集合中要删除该数。这样我们调用min函数的时候，只需要得到list最后一个元素即可。

代码

先用starUML设计类图

根据类图设计代码：

package com.sprd.interview.algorithm;import java.util.ArrayList;
import java.util.List;/*** Copyright 2014 TJ SPREADTRUM TEST_AF All Right Reserved* * @author: hui.qian Created on 2014年12月10日 上午10:08:42 Description:*/
public class QHStack {List<Integer> mStack;List<Integer> mMins;int stackTopElement;int minElement;/*** 初始化栈信息*/public void initStack() {mStack = new ArrayList<Integer>();mMins = new ArrayList<Integer>();}/*** 销毁栈*/public void destoryStack() {if (mStack != null) {mStack.clear();mStack = null;}if (mMins != null) {mMins.clear();mMins = null;}}public void push(int newElement) {checkInit();if (isMin(minElement, newElement)) {mMins.add(newElement);minElement = newElement;}mStack.add(newElement);stackTopElement = newElement;}/*** 获得栈中最小元素*/public int min() {checkInit();return minElement;}/*** 获得栈顶元素并删除它*/public int pop() {checkInit();int num = stackTopElement;if (stackTopElement == minElement) {mStack.remove(stackTopElement);mMins.remove(minElement);stackTopElement = mStack.get(mStack.size() - 1);minElement = mMins.get(mMins.size() - 1);}return num;}/*** 判断栈是否为空*/public boolean isEmpty() {if (mStack == null)return false;return mStack.isEmpty();}/*** 获得栈顶元素*/public int getTop() {checkInit();return stackTopElement;}/*** 获得栈的大小*/public int stackLength() {checkInit();return mStack.size();}/*** 检查是否已初始化栈*/private void checkInit() {if (mStack == null) {throw new IllegalArgumentException();}}/*** 判断新元素是否比当前最小数小*/private boolean isMin(int min, int newElement) {if (newElement <= min) {return true;}return false;}}