把每次的最小元素(之前的最小元素和新壓入戰(zhàn)的元素兩者的較小值)都保存起來放到另外一個輔助棧里。
如果每次都把最小元素壓入輔助棧, 那么就能保證輔助棧的棧頂一直都是最小元素.當(dāng)最小元素從數(shù)據(jù)棧內(nèi)被彈出之后,同時彈出輔助棧的棧頂元素,此時輔助棧的新棧頂元素就是下一個最小值。
public class Test21 {
/**
* 定義棧的數(shù)據(jù)結(jié)構(gòu),請在該類型中實現(xiàn)一個能夠得到校的最小元素的min函數(shù)。
* 在該棧中,調(diào)用pop、push 及min的時間復(fù)雜度都是0(1)
*
* @param <T> 泛型參數(shù)
*/
public static class StackWithMin<T extends Comparable<T>> {
// 數(shù)據(jù)棧,用于存放插入的數(shù)據(jù)
private Stack<T> dataStack;
// 最小數(shù)位置棧,存放數(shù)據(jù)棧中最小的數(shù)的位置
private Stack<Integer> minStack;
// 構(gòu)造函數(shù)
public StackWithMin() {
this.dataStack = new Stack<>();
this.minStack = new Stack<>();
}
/**
* 出棧方法
* @return 棧頂元素
*/
public T pop() {
// 如果棧已經(jīng)為空,再出棧拋出異常
if (dataStack.isEmpty()) {
throw new RuntimeException("The stack is already empty");
}
// 如果有數(shù)據(jù),最小數(shù)位置棧和數(shù)據(jù)棧必定是有相同的元素個數(shù),
// 兩個棧同時出棧
minStack.pop();
return dataStack.pop();
}
/**
* 元素入棧
* @param t 入棧的元素
*/
public void push(T t) {
// 如果入棧的元素為空就拋出異常
if (t == null) {
throw new RuntimeException("Element can be null");
}
// 如果數(shù)據(jù)棧是空的,只接將元素入棧,同時更新最小數(shù)棧中的數(shù)據(jù)
if (dataStack.isEmpty()) {
dataStack.push(t);
minStack.push(0);
}
// 如果數(shù)據(jù)棧中有數(shù)據(jù)
else {
// 獲取數(shù)據(jù)棧中的最小元素(未插入t之前的)
T e = dataStack.get(minStack.peek());
// 將t入棧
dataStack.push(t);
// 如果插入的數(shù)據(jù)比棧中的最小元素小
if (t.compareTo(e) < 0) {
// 將新的最小元素的位置入最小棧
minStack.push(dataStack.size() - 1);
} else {
// 插入的元素不比原來的最小元素小,復(fù)制最小棧棧頂元素,將其入棧
minStack.push(minStack.peek());
}
}
}
/**
* 獲取棧中的最小元素
* @return 棧中的最小元素
*/
public T min() {
// 如果最小數(shù)公位置棧已經(jīng)為空(數(shù)據(jù)棧中已經(jīng)沒有數(shù)據(jù)了),則拋出異常
if (minStack.isEmpty()) {
throw new RuntimeException("No element in stack.");
}
// 獲取數(shù)據(jù)棧中的最小元素,并且返回結(jié)果
return dataStack.get(minStack.peek());
}
}
public static void main(String[] args) {
StackWithMin<Integer> stack = new StackWithMin<>();
stack.push(3);
System.out.println(stack.min() == 3);
stack.push(4);
System.out.println(stack.min() == 3);
stack.push(2);
System.out.println(stack.min() == 2);
stack.push(3);
System.out.println(stack.min() == 2);
stack.pop();
System.out.println(stack.min() == 2);
stack.pop();
System.out.println(stack.min() == 3);
stack.push(0);
System.out.println(stack.min() == 0);
}
}
http://wiki.jikexueyuan.com/project/for-offer/images/28.png" alt="" />