題目
實現(xiàn)一個特殊的棧姚炕，在實現(xiàn)棧的基礎上征唬，再實現(xiàn)返回棧中最小的元素的操作菩咨。
要求
- pop疫诽、push、getMin的時間復雜度是O(1)
- 可以使用現(xiàn)成的棧類型
思路
如下圖所示旦委，在棧結構中奇徒，每次pop的過程中，產生的最小值缨硝，分別為：1摩钙、2、6查辩，在pop過程會出現(xiàn)兩個規(guī)律：
- 每次pop的元素不是最小值時胖笛，整個棧的最小值保持不變网持，
- 越上的最小值越小
那么只需要引入多一個棧（minElementStack），在push時长踊，在minElementStack的棧頂里面保存比當前最小值還小的元素就可以了功舀，而minElementStack的棧頂始終保持當前棧中最小的元素。在pop時身弊，當pop掉棧的最小值元素辟汰，只需同時pop掉minElementStack中的元素就好了。
棧結構
代碼
package com.github.zhanyongzhi.interview.algorithm.stacklist;
import java.util.Stack;
/**
* 帶有getMin的棧
* @author zhanyongzhi
*/
public class GetMinStack<T extends Comparable<T>> {
Stack<T> stack;
Stack<T> minElementStack;
public GetMinStack(){
stack = new Stack<T>();
minElementStack = new Stack<T>();
}
public void push(T item) {
stack.push(item);
if(minElementStack.empty()) {
minElementStack.push(item);
return;
}
T topItem = getMin();
if(0 <= item.compareTo(topItem))
return;
//當前加入的元素是最小的則加入到minElementStack中
minElementStack.push(item);
}
public T pop(){
T item = stack.pop();
T topItem = getMin();
//如果當前彈出的是最小的元素
if(topItem.equals(item))
minElementStack.pop();
return item;
}
public T getMin(){
return minElementStack.peek();
}
}
