带最小值操作的栈

题目描述

实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。
你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。

思路

考虑用ArrayList实现栈操作，配合队列的get\remove方法实现push\pop操作
实现取最小值功能需要注意：
虽然可以简单的用一个变量保存list中的最小元素，但当该元素pop后怎么办呢？
解决办法：
用另一个list保存list中的最小值，每次push，如果值不大于list末尾的值，则添加到list中。
每次pop，如果pop的值与List末尾元素相等，则删除该元素
这样做，保证了此list末尾元素始终保存当前栈内最小值

代码

ArrayList<Integer> aList;
	ArrayList<Integer> minList;
	
	public MinStack() {
		this.aList = new ArrayList<>();
		this.minList = new ArrayList<>();
	}

	public void push(int number) {
		if (aList.size() == 0) {
			aList.add(number);
			minList.add(number);
		} else {
			aList.add(number);
			if (number <= minList.get(minList.size()-1)) {
				minList.add(number);
			}
		}
	}

	public int pop() {
		int popNum = aList.remove(aList.size()-1);
		if(popNum == minList.get(minList.size()-1)) {
			minList.remove(minList.size()-1);
		}
		return popNum;
	}
    
    public int min() {
	    return minList.get(minList.size()-1);
	}

考察点

• 栈的实现