原标题：https://oj.leetcode.com/problems/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.
题目事实上不难。可是是leetCode今天刚刚新增的一个题目。索性抢个头彩把解题过程分享出来：
直接上AC代码：
public class MinStack {
private int min = Integer.MAX_VALUE;
private int minIndex = -1;
private ArrayList<Integer> stack = new ArrayList<Integer>();
private int length = 0;
private HashMap<Integer,Integer> secondMinMap = new HashMap<Integer, Integer>();
public void push(int x) {
stack.add(x);
if(x <= min) { //注意这里犯过错误，须要加=号，原因是当栈空的时候假设push一个Integer.MaxValue的话。须要将此时的minIndex变为0而不是继续为-1。
//否则的话。这样的情况下。当push第二个数的时候，将出现secondMap.put(1,-1)的情况，进而当pop这个数的时候，会出现stack.get(-1)操作。
//换句话说。这个secondMap里的值仅仅有当key=0的时候。才干为-1，其它情况必须有能指向数组里位置的值
secondMinMap.put(length, minIndex); //这里存的 length位置相应的第二小的，仅仅考虑比length小的索引即可
//由于用到的场景是当前这个假设被pop了，说明它上面的全部都已经被pop了
//这个时候假设当前是min。那么接下来仅仅须要在它以下去找第二小的即可了
minIndex = length;
min = x;
}
length ++;
}
public void pop() {
if(length == 0) return;
if(minIndex == length-1) {
if(minIndex == 0) {
minIndex = -1;
min = Integer.MAX_VALUE;
} else {
minIndex = secondMinMap.get(length-1);
secondMinMap.remove(length-1);
min = stack.get(minIndex);
}
}
stack.remove(length-1);
length--;
}
public int top() {
return stack.get(length-1);
}
public int getMin() {
return min;
}
public static void main(String[] args) {
MinStack stack = new MinStack();
stack.push(2147483646);
stack.push(2147483646);
stack.push(2147483647);
System.out.println(stack.top());
stack.pop();
System.out.println(stack.getMin());
stack.pop();
System.out.println(stack.getMin());
stack.pop();
stack.push(2147483647);
System.out.println(stack.top());
System.out.println(stack.getMin());
stack.push(-2147483648);
System.out.println(stack.top());
System.out.println(stack.getMin());
stack.pop();
System.out.println(stack.getMin());
}
}
版权声明：本文博主原创文章。博客，未经同意不得转载。